Алгоритм Флойда-Уоршолла — различия между версиями

Версия 19:47, 23 октября 2008

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

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

def floyd_warshal(D):
    N=D.shape[0]  
    print_frame(D)                
    for k in xrange(N):
        #Сохраняем $D_{k-1}$ в $D_{old}$
        D_old=array(D)              
        for v1 in xrange(N):
            for v2 in xrange (N):
                D[v1,v2]=min( D[v1,v2], D_old[v1,k]+D_old[k,v2] )    
        print_frame(D,D_old,k)                
    return D

Трассировка алгоритма

Входной граф

Итерация 1

Итерация 2

Итерация 3

Итерация 4

Итерация 5

Итерация 6