|
Поиск кратчайших путей:алгоритм Флойда-Уоршолла — различия между версиями
Материал из CustisWiki
|
|
| (не показана 1 промежуточная версия 1 участника) | | Строка 1: |
Строка 1: |
| − | Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи поиска кратчайших путей в графе — ''Shortest Path Problem''. В отличие от [[Поиск кратчайших путей:алгоритм Дейкстры|алгоритма Дейкстры]], он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми пунктами).
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | | + | |
| − | В этом алгоритме, для графа <math>G=(V,E)</math> последовательно выполняются <math>n=|V|</math> итераций, улучшая матрицу <math>D_{ij}</math> минимальных стоимостей пути из вершины ''i'' в вершину ''j'', с возможным использованием (для ''k''-той итерации) промежуточных вершин из множества <math>1,\dots,k</math>. Вычислять эту матрицу очень легко, изначально она определяется весовой функцией ребер, <math>D^0_{ij}=w_{ij}</math>, для тех ''i'' и ''j'', для которых есть ребро ''(i,j)'', и <math>+\infty</math> для остальных.
| + | |
| − | Обновление этой матрицы на ''k''-той итерации происходит по очевидной формуле:
| + | |
| − | <math>D^k_{ij}=min(D^{k-1}_{ij},D^{k-1}_{ik}+D^{k-1}_{kj})</math>, где <math>D^{k-1}</math> — значение этой матрицы на предыдущей итерации.
| + | |
| − | Таким образом, очевидна и корректность алгоритма, и его сложность, состовляющая <math>O(n^3)</math>.
| + | |
| − | | + | |
| − | <code-python>
| + | |
| − | # Находит стоимость кратчайшего пути для всех пар вершин. | + | |
| − | # Выбор и хранение самих оптимальных путей не показаны для простоты.
| + | |
| − | 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
| + | |
| − | </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,]]
| + | |
| − | | + | |
| − | | + | |
| − | <graphviz>
| + | |
| − | digraph G{ rankdir=TB;
| + | |
| − | 0 [label="NY(0)"];
| + | |
| − | 1 [label="Moscow(1)"];
| + | |
| − | 2 [label="Minsk(2)"];
| + | |
| − | 3 [label="Berlin(3)"];
| + | |
| − | 4 [label="Kiev(4)"];
| + | |
| − | 0 -> 4[fontcolor="blue",label="$80",style=solid];
| + | |
| − | 1 -> 0[fontcolor="blue",label="$60",style=solid];
| + | |
| − | 3 -> 0[fontcolor="blue",label="$50",style=solid];
| + | |
| − | 1 -> 2[fontcolor="blue",label="$-5",style=solid];
| + | |
| − | 1 -> 3[fontcolor="blue",label="$50",style=solid];
| + | |
| − | 1 -> 4[fontcolor="blue",label="$10",style=solid];
| + | |
| − | 2 -> 1[fontcolor="blue",label="$10",style=solid];
| + | |
| − | 3 -> 1[fontcolor="blue",label="$30",style=solid];
| + | |
| − | 4 -> 1[fontcolor="blue",label="$15",style=solid];
| + | |
| − | 3 -> 2[fontcolor="blue",label="$20",style=solid];
| + | |
| − | 4 -> 2[fontcolor="blue",label="$15",style=solid];
| + | |
| − | 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];
| + | |
| − | } | + | |
| − | </graphviz>
| + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | [[Category:Алгоритмы]]
| + | |
| − | | + | |
| − | {{replicate-from-custiswiki-to-lib}}
| + | |
Текущая версия на 20:45, 13 июня 2011
- REDIRECT discopal:Поиск кратчайших путей:алгоритм Флойда-Уоршолла
|
 |
