Алгоритм Флойда-Уоршелла

Алгоритмы   7 января 2012  Автор статьи:  

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

Алгоритм решения

Пусть веса дуг заданы в виде матрицы D. Будем решать задачу методом динамического программирования. Обозначим за T_{i,j,k} длину кратчайшего пути между вершинами i и j, который в качестве промежуточных содержит только вершины с номерами, не превосходящими k. Рассмотрим случай, когда k=0. Это означает, что промежуточных вершин в путях быть не может. Значит, путь будет существовать между теми вершинами, между которыми по условию есть дуга. Тогда матрицу T_{i,j,0} построим на основе матрицы D следующим образом. Во-первых, расстояние между вершинами, между которыми нет дуги, положим равным бесконечности. Во-вторых, из вершины в неё саму всегда можно добраться за нулевое число шагов, поэтому если вес дуги (i,i)  положителен, то заменим его нулём. Пусть теперь k>0. Понятно, что искомый кратчайший путь может либо проходить через вершину с номером k, либо нет. Если он проходит через эту вершину, то его можно разбить на две части: путь от i до k и путь от k до j. Поскольку оба этих пути должны являться кратчайшими, имеем следующее рекуррентное соотношение:

T_{i,j,k}=\begin{cases}\infty ,\text{ if }k=0,\; \,i\ne j,\,\; (i,j)\;\not \in \;E; \\\min(D_{i,j},0),\text{ if }k=0,\,i=j; \\\min(T_{i,j,k-1}, T_{i,k,k-1}+T_{k,j,k-1}),\text{ if }k > 0. \\\end{cases}

Асимптотическая сложность алгоритма – O(N^3), где N – число вершин графа.

Так же, как и в алгоритме Форда-Беллмана, объём используемой памяти можно сократить. Нам достаточно одной матрицы размерности N. Все обновления расстояний мы будем осуществлять именно в ней.

Отметим, что при наличии в графе циклов отрицательного веса существуют кратчайшие пути сколь угодно малого веса. Имеет место следующий критерий: в графе есть циклы отрицательного веса тогда и только тогда, когда для некоторого i T_{i,i,n}<0 .

Данный алгоритм был разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом (иногда встречаются другие варианты перевода фамилии Warshall).

Автор статьи – Сухов Сергей

Научиться программировать

  • на Delphi

  • на Java

  • на C++