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