флеров

Нахождение кратчайших путей в графе

В этом разделе мы будем рассматривать ориентированные графы G = <V, E >, ребрам которых приписаны веса. Это означает, что каждому ребру поставлено в соответствие вещественное число c(u,v), называемое весом данного ребра. Полагаем, что с(u, v) =, если <u, v>E.

Если S = <v₀, v₁, ... , v_p>- путь в G, то его длина определяется как сумма

(Отметим, что если в произвольном графе мы примем вес каждого ребра равным единице, то получим обычное определение длины пути как числа ребер).

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами Длину такого кратчайшего пути d(v,t) и будем называть расстоянием от v до t . Отметим, что если каждый цикл нашего графа имеет положительную длину, то кратчайший путь будет всегда простым.

Во многих приложениях достаточно находить кратчайшие пути между двумя конкретными вершинами, однако, неизвестен алгоритм, который решал бы эту задачу эффективнее (в худшем случае), чем лучший из известных алгоритмов для нахождения кратчайших расстояний от одной вершины v₀, называемой источником, до всех остальных вершин.

Задача нахождения кратчайших путей от одного источника решается для трех случаев.

1. Ориентированный граф без циклов с отрицательной длиной (cложность алгоритма - , где n - число вершин).

2. Веса всех ребер неотрицательны (cложность алгоритма - ).

3. Граф без циклов (cложность алгоритма - ).

Рассмотрим второй случай.

Содержание