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

В предыдущем разделе был рассмотрен алгоритм Дейкстры, позволяющий находить кратчайшие пути в графе из начальной вершины до конечной вершины или до всех других вершин. Теперь рассмотрим задачу поиска кратчайших путей между каждой парой вершин. Решить её можно, применив алгоритм Дейкстры для каждой вершины, то есть в качестве начальной брать по очереди все вершины графа и находить кратчайшие пути из начальной вершины до всех других вершин. Такой подход для графа G =(V, E) с неотрицательными весами дуг дал бы алгоритм с трудоемкостью О(| V |³). Однако для нахождения кратчайших путей между каждой парой вершин существует более общий метод (алгоритм Флойда), требующий О(| V |³) операций даже для графов с отрицательными весами дуг.

Пусть W =║ w_ij ║- матрица весов графа G =(V, E), и мы хотим вычислить матрицу W ^*=║ w_ij ^*║, в которой w_ij ^* - длина кратчайшего пути из i Î V в j Î V.

Аналогично методу вычисления транзитивного замыкания (разд. 3.2.4) можно вычислить матрицу W ^*, определив последовательность матриц W ⁽⁰⁾=║ w_ij ⁽⁰⁾║, W ⁽¹⁾=║ w_ij ⁽¹⁾║,¼, W ^(|V|)=║ w_ij ^(|V|)║, следующим образом:

1) w_ij ⁽⁰⁾= w_ij;

2) w_ij ^{( k )}=min{ w_ij ^{( k -1)}, w_ik ^{( k -1)}+ w_kj ^{( k -1)}}.

Утверждение: Значение w_ij ^{( k )} есть длина кратчайшего пути из вершины i Î V в вершину j Î V с промежуточными вершинами, принадлежащими множеству {1,2,¼, k }Í V. Тогда W ^{(| V |)} – матрица кратчайших путей, а элемент матрицы w_ij равен длине кратчайшего пути из вершины i в вершину j.

Доказательство данного утверждения проводится методом математической индукции, аналогично доказательству утверждения в разд.3.2.4.

Алгоритм 4.Алгоритм Флойда

Алгоритм следует из выражения 6.2

for k = 1 to | V | do

for i = 1 to | V | do

for j = 1 to | V | do

w_ij min{ w_ij, w_ik + w_kj }

Заметим, что на алгоритм отрицательность весов не влияет, но если в графе имеется контур отрицательной длины, то алгоритм не работает. Также отметим, что данный алгоритм является более эффективным для вычисления единственного кратчайшего пути в плотном орграфе, чем алгоритм Форда.