Текст:Поиск кратчайших путей: алгоритм Флойда-Уоршолла

Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи поиска кратчайших путей в графе — Shortest Path Problem. В отличие от алгоритма Дейкстры, он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми точками).

В этом алгоритме, для графа $G=(V,E)$ последовательно выполняются $n=|V|$ итераций, улучшая матрицу $D_{ij}$ минимальных стоимостей пути из вершины i в вершину j, с возможным использованием (для k-той итерации) промежуточных вершин из множества $1,\dots,k$. Вычислять эту матрицу очень легко, изначально она определяется весовой функцией ребер, $D^0_{ij}=w_{ij}$, для тех i и j, для которых есть ребро (i,j), и $+\infty$ для остальных. Обновление этой матрицы на k-той итерации происходит по очевидной формуле: $D^k_{ij}=min(D^{k-1}_{ij},D^{k-1}_{ik}+D^{k-1}_{kj})$, где $D^{k-1}$ — значение этой матрицы на предыдущей итерации. Таким образом, очевидна и корректность алгоритма, и его сложность, состовляющая $O(n^3)$.

<code-python>

1. Находит стоимость кратчайшего пути для всех пар вершин.
2. Выбор и хранение самих оптимальных путей не показаны для простоты.

def floyd_warshal(G):

   N = G.number_of_nodes()
   # Инициализируем матрицу $D$ расстояниями, используем $777$ как $\infty$.
   D = (ones((N,N))-identity(N))*777
   for e in G.edges():
       D[e[0],e[1]]=e[2]
   print D    
   for k in range(0,N):
       print; print "Iteration: k=",k
       D_old=array(D)              #Сохраняем $D_{k-1}$ в $D_{old}$
       for v1 in range(0,N):
           for v2 in range (0,N):
               D[v1,v2]=min(D[v1,v2],D_old[v1,k]+D_old[k,v2])    
       if D<>D_old:
           print D-D_old        
       else:
           print "D remains unchanged"
   print; print; print D
   return D

</code-python>

[[  0,777,777,777, 80,]
 [ 60,  0, -5, 50, 10,]
 [777, 10,  0,777,777,]
 [ 50, 30, 20,  0, 30,]
 [777, 15, 15,777,  0,]]

Iteration: k= 0
D remains unchanged

Iteration: k= 1
[[   0,   0,  -5,   0,   0,]
 [   0,   0,   0,   0,   0,]
 [-707,   0,   0,-717,-757,]
 [   0,   0,   0,   0,   0,]
 [-702,   0,  -5,-712,   0,]]

Iteration: k= 2
D remains unchanged

Iteration: k= 3
D remains unchanged

Iteration: k= 4
[[   0,-682,-682,-632,   0,]
 [   0,   0,   0,   0,   0,]
 [   0,   0,   0,   0,   0,]
 [   0,   0,   0,   0,   0,]
 [   0,   0,   0,   0,   0,]]

[[  0, 95, 90,145, 80,]
 [ 60,  0, -5, 50, 10,]
 [ 70, 10,  0, 60, 20,]
 [ 50, 30, 20,  0, 30,]
 [ 75, 15, 10, 65,  0,]]

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.