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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

В этом алгоритме, для графа \(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)\).

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

Трассировка алгоритма[править]

Входной граф[править]

Graph image creation requires permission to upload.

Итерация 1[править]

\( \begin{tabular}{|p{.18\textwidth}|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|} \hline & NY & Moscow & Minsk & Berlin & Kiev \\ \hline NY & \hfill 0 & \hfill $\infty$ & \hfill $\infty$ & \hfill $\infty$ & \hfill 80 \\ \hline Moscow & \hfill 60 & \hfill 0 & \hfill -5 & \hfill 50 & \hfill 10 \\ \hline Minsk & \hfill $\infty$ & \hfill 10 & \hfill 0 & \hfill $\infty$ & \hfill $\infty$ \\ \hline Berlin & \hfill 50 & \hfill 30 & \hfill 20 & \hfill 0 & \hfill 30 \\ \hline Kiev & \hfill $\infty$ & \hfill 15 & \hfill 15 & \hfill $\infty$ & \hfill 0 \\ \hline \end{tabular} \)

Итерация 2[править]

\( \begin{tabular}{|p{.18\textwidth}|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|} \hline k=0 (NY) & NY & Moscow & Minsk & Berlin & Kiev \\ \hline NY & \hfill 0 & \hfill $\infty$ & \hfill $\infty$ & \hfill $\infty$ & \hfill 80 \\ \hline Moscow & \hfill 60 & \hfill 0 & \hfill -5 & \hfill 50 & \hfill 10 \\ \hline Minsk & \hfill $\infty$ & \hfill 10 & \hfill 0 & \hfill $\infty$ & \hfill $\infty$ \\ \hline Berlin & \hfill 50 & \hfill 30 & \hfill 20 & \hfill 0 & \hfill 30 \\ \hline Kiev & \hfill $\infty$ & \hfill 15 & \hfill 15 & \hfill $\infty$ & \hfill 0 \\ \hline \end{tabular} \)

Итерация 3[править]

\( \begin{tabular}{|p{.18\textwidth}|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|} \hline k=1 (Moscow) & NY & Moscow & Minsk & Berlin & Kiev \\ \hline NY & \hfill 0 & \hfill $\infty$ & \hfill $\infty$ & \hfill $\infty$ & \hfill 80 \\ \hline Moscow & \hfill 60 & \hfill 0 & \hfill -5 & \hfill 50 & \hfill 10 \\ \hline Minsk & \hfill \textcolor{red}{$\infty$}$\Rightarrow$\textbf{70 } & \hfill 10 & \hfill 0 & \hfill \textcolor{red}{$\infty$}$\Rightarrow$\textbf{60 } & \hfill \textcolor{red}{$\infty$}$\Rightarrow$\textbf{20 } \\ \hline Berlin & \hfill 50 & \hfill 30 & \hfill 20 & \hfill 0 & \hfill 30 \\ \hline Kiev & \hfill \textcolor{red}{$\infty$}$\Rightarrow$\textbf{75 } & \hfill 15 & \hfill \textcolor{red}{15}$\Rightarrow$\textbf{10 } & \hfill \textcolor{red}{$\infty$}$\Rightarrow$\textbf{65 } & \hfill 0 \\ \hline \end{tabular} \)

Итерация 4[править]

\( \begin{tabular}{|p{.18\textwidth}|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|} \hline k=2 (Minsk) & NY & Moscow & Minsk & Berlin & Kiev \\ \hline NY & \hfill 0 & \hfill $\infty$ & \hfill $\infty$ & \hfill $\infty$ & \hfill 80 \\ \hline Moscow & \hfill 60 & \hfill 0 & \hfill -5 & \hfill 50 & \hfill 10 \\ \hline Minsk & \hfill 70 & \hfill 10 & \hfill 0 & \hfill 60 & \hfill 20 \\ \hline Berlin & \hfill 50 & \hfill 30 & \hfill 20 & \hfill 0 & \hfill 30 \\ \hline Kiev & \hfill 75 & \hfill 15 & \hfill 10 & \hfill 65 & \hfill 0 \\ \hline \end{tabular} \)

Итерация 5[править]

\( \begin{tabular}{|p{.18\textwidth}|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|} \hline k=3 (Berlin) & NY & Moscow & Minsk & Berlin & Kiev \\ \hline NY & \hfill 0 & \hfill $\infty$ & \hfill $\infty$ & \hfill $\infty$ & \hfill 80 \\ \hline Moscow & \hfill 60 & \hfill 0 & \hfill -5 & \hfill 50 & \hfill 10 \\ \hline Minsk & \hfill 70 & \hfill 10 & \hfill 0 & \hfill 60 & \hfill 20 \\ \hline Berlin & \hfill 50 & \hfill 30 & \hfill 20 & \hfill 0 & \hfill 30 \\ \hline Kiev & \hfill 75 & \hfill 15 & \hfill 10 & \hfill 65 & \hfill 0 \\ \hline \end{tabular} \)

Итерация 6[править]

\( \begin{tabular}{|p{.18\textwidth}|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|p{.14\textwidth}|r|} \hline k=4 (Kiev) & NY & Moscow & Minsk & Berlin & Kiev \\ \hline NY & \hfill 0 & \hfill \textcolor{red}{$\infty$}$\Rightarrow$\textbf{95 } & \hfill \textcolor{red}{$\infty$}$\Rightarrow$\textbf{90 } & \hfill \textcolor{red}{$\infty$}$\Rightarrow$\textbf{145 } & \hfill 80 \\ \hline Moscow & \hfill 60 & \hfill 0 & \hfill -5 & \hfill 50 & \hfill 10 \\ \hline Minsk & \hfill 70 & \hfill 10 & \hfill 0 & \hfill 60 & \hfill 20 \\ \hline Berlin & \hfill 50 & \hfill 30 & \hfill 20 & \hfill 0 & \hfill 30 \\ \hline Kiev & \hfill 75 & \hfill 15 & \hfill 10 & \hfill 65 & \hfill 0 \\ \hline \end{tabular} \)
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.