Алгоритм Флойда-Уоршолла — различия между версиями
BenderBot (обсуждение | вклад) м (реплицировано из внутренней CustisWiki) |
BenderBot (обсуждение | вклад) м (реплицировано из внутренней CustisWiki) |
||
(не показана 1 промежуточная версия 1 участника) | |||
Строка 8: | Строка 8: | ||
<code-python> | <code-python> | ||
− | def floyd_warshal( | + | # Находит стоимость кратчайшего пути для всех пар вершин. |
− | N=D. | + | # Выбор и хранение самих оптимальных путей не показаны для простоты. |
− | + | def floyd_warshal(G): | |
− | for k in | + | N = G.number_of_nodes() |
− | #Сохраняем $D_{k-1}$ в $D_{old}$ | + | # Инициализируем матрицу $D$ расстояниями, используем $777$ как $\infty$. |
− | + | D = (ones((N,N))-identity(N))*777 | |
− | for v1 in | + | for e in G.edges(): |
− | for v2 in | + | D[e[0],e[1]]=e[2] |
− | D[v1,v2]=min( D[v1,v2], D_old[v1,k]+D_old[k,v2] ) | + | 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 | 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= | + | digraph G{ rankdir=TB; |
− | + | ||
− | + | ||
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> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | [[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,]]
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «Алгоритм Флойда-Уоршолла»