Поиск кратчайших путей:алгоритм Флойда-Уоршолла — различия между версиями

Текущая версия на 21:12, 20 июня 2006

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

В этом алгоритме, для графа последовательно выполняются итераций, улучшая матрицу минимальных стоимостей пути из вершины i в вершину j, с возможным использованием (для k-той итерации) промежуточных вершин из множества . Вычислять эту матрицу очень легко, изначально она определяется весовой функцией ребер, , для тех i и j, для которых есть ребро (i,j), и для остальных. Обновление этой матрицы на k-той итерации происходит по очевидной формуле: , где — значение этой матрицы на предыдущей итерации. Таким образом, очевидна и корректность алгоритма, и его сложность, состовляющая .

# Находит стоимость кратчайшего пути для всех пар вершин.
# Выбор и хранение самих оптимальных путей не показаны для простоты. 
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

[[  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,]]