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

Материал из CustisWiki
Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
(обновление. улучшение иллюстраций.)
Строка 8: Строка 8:
  
 
<code-python>
 
<code-python>
−
# Находит стоимость кратчайшего пути для всех пар вершин.
+
def floyd_warshal(D):
−
# Выбор и хранение самих оптимальных путей не показаны для простоты.
+
     N=D.shape[0]
−
def floyd_warshal(G):
+
     print_frame(D)               
−
     N = G.number_of_nodes()
+
     for k in xrange(N):
−
    # Инициализируем матрицу $D$ расстояниями, используем $777$ как $\infty$.
+
         #Сохраняем $D_{k-1}$ в $D_{old}$
−
    D = (ones((N,N))-identity(N))*777
+
        D_old=array(D)             
−
    for e in G.edges():
+
         for v1 in xrange(N):
−
        D[e[0],e[1]]=e[2]
+
             for v2 in xrange (N):
−
     print D  
+
                 D[v1,v2]=min( D[v1,v2], D_old[v1,k]+D_old[k,v2] )     
−
     for k in range(0,N):
+
         print_frame(D,D_old,k)               
−
         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
 
     return D
 
</code-python>
 
</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,]]
+
−
 
+
  
 +
===Входной граф===
 
<graph>
 
<graph>
−
digraph G{ rankdir=TB;  
+
digraph G{ rankdir=LR;
 +
  node[fontsize=16];
 +
  edge[fontcolor=blue,style=dashed];
 
  0 [label="NY(0)"];
 
  0 [label="NY(0)"];
 
  1 [label="Moscow(1)"];
 
  1 [label="Moscow(1)"];
Строка 74: Строка 33:
 
  3 [label="Berlin(3)"];
 
  3 [label="Berlin(3)"];
 
  4 [label="Kiev(4)"];
 
  4 [label="Kiev(4)"];
−
  0 -> 4[fontcolor="blue",label="$80",style=solid];  
+
  0 -> 4[label="$80"];  
−
  1 -> 0[fontcolor="blue",label="$60",style=solid];  
+
  1 -> 0[label="$60"];  
−
  3 -> 0[fontcolor="blue",label="$50",style=solid];  
+
  3 -> 0[label="$50"];  
−
  1 -> 2[fontcolor="blue",label="$-5",style=solid];  
+
  1 -> 2[label="$-5"];  
−
  1 -> 3[fontcolor="blue",label="$50",style=solid];  
+
  1 -> 3[label="$50"];  
−
  1 -> 4[fontcolor="blue",label="$10",style=solid];  
+
  1 -> 4[label="$10"];  
−
  2 -> 1[fontcolor="blue",label="$10",style=solid];  
+
  2 -> 1[label="$10"];  
−
  3 -> 1[fontcolor="blue",label="$30",style=solid];  
+
  3 -> 1[label="$30"];  
−
  4 -> 1[fontcolor="blue",label="$15",style=solid];  
+
  4 -> 1[label="$15"];  
−
  3 -> 2[fontcolor="blue",label="$20",style=solid];  
+
  3 -> 2[label="$20"];  
−
  4 -> 2[fontcolor="blue",label="$15",style=solid];  
+
  4 -> 2[label="$15"];  
−
  3 -> 4[fontcolor="blue",label="$30",style=solid];
+
  3 -> 4[label="$30"];  
−
0 -> 1[fontcolor="red",label="$95",style=dashed];
+
−
0 -> 2[fontcolor="red",label="$90",style=dashed];
+
−
0 -> 3[fontcolor="red",label="$145",style=dashed];
+
−
2 -> 0[fontcolor="red",label="$70",style=dashed];
+
−
2 -> 3[fontcolor="red",label="$60",style=dashed];
+
−
2 -> 4[fontcolor="red",label="$20",style=dashed];
+
−
4 -> 0[fontcolor="red",label="$75",style=dashed];
+
−
4 -> 2[fontcolor="red",label="$10",style=dashed];
+
−
4 -> 3[fontcolor="red",label="$65",style=dashed];  
+
 
}  
 
}  
 
</graph>
 
</graph>
  
  
 +
===Итерация 1===
 +
<latex>
 +
 +
\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}
 +
</latex>
 +
 +
===Итерация 2===
 +
<latex>
 +
 +
\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}
 +
</latex>
 +
 +
===Итерация 3===
 +
<latex>
 +
 +
\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}
 +
</latex>
 +
 +
===Итерация 4===
 +
<latex>
 +
 +
\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}
 +
</latex>
  
 +
===Итерация 5===
 +
<latex>
  
 +
\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}
 +
</latex>
  
 +
===Итерация 6===
 +
<latex>
 +
\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}
 +
</latex>
  
−
[[Category:Алгоритмы]]
 
  
 +
[[Category:Алгоритмы|Ф]]
 
{{replicate-from-custiswiki-to-lib}}
 
{{replicate-from-custiswiki-to-lib}}

Версия 16:23, 5 марта 2007

Алгоритм Флойда-Уоршолла (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

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

Входной граф

[svg]


Итерация 1

Итерация 2

Итерация 3

Итерация 4

Итерация 5

Итерация 6

Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «Алгоритм Флойда-Уоршолла»

Источник — «http://lib.custis.ru/index.php?title=Алгоритм_Флойда-Уоршолла&oldid=9790»