Поиск кратчайших путей:алгоритм Флойда-Уоршолла - История изменений

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:45:23Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

AntMatrik в 21:12, 20 июня 2006

2006-06-20T21:12:26Z

Новая страница

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

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

BenderBot: реплицировано из внутренней CustisWiki

2005-08-10T00:41:31Z

реплицировано из внутренней CustisWiki

← Предыдущая		Версия 00:41, 10 августа 2005
Строка 1:		Строка 1:
−	Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи поиска кратчайших путей в графе — ''Shortest Path Problem''. В отличие от [[Поиск кратчайших путей:алгоритм Дейкстры\|алгоритма Дейкстры]], он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми ~~точками~~).	+	Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи поиска кратчайших путей в графе — ''Shortest Path Problem''. В отличие от [[Поиск кратчайших путей:алгоритм Дейкстры\|алгоритма Дейкстры]], он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми пунктами).

	В этом алгоритме, для графа <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> для остальных.		В этом алгоритме, для графа <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> для остальных.

@@ Строка 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;
-[label="NY(0)"];
-[label="Moscow(1)"];
-[label="Minsk(2)"];
-[label="Berlin(3)"];
-[label="Kiev(4)"];
--> 4[fontcolor="blue",label="$80",style=solid];
--> 0[fontcolor="blue",label="$60",style=solid];
--> 0[fontcolor="blue",label="$50",style=solid];
--> 2[fontcolor="blue",label="$-5",style=solid];
--> 3[fontcolor="blue",label="$50",style=solid];
--> 4[fontcolor="blue",label="$10",style=solid];
--> 1[fontcolor="blue",label="$10",style=solid];
--> 1[fontcolor="blue",label="$30",style=solid];
--> 1[fontcolor="blue",label="$15",style=solid];
--> 2[fontcolor="blue",label="$20",style=solid];
--> 2[fontcolor="blue",label="$15",style=solid];
--> 4[fontcolor="blue",label="$30",style=solid];
--> 1[fontcolor="red",label="$95",style=dashed];
--> 2[fontcolor="red",label="$90",style=dashed];
--> 3[fontcolor="red",label="$145",style=dashed];
--> 0[fontcolor="red",label="$70",style=dashed];
--> 3[fontcolor="red",label="$60",style=dashed];
--> 4[fontcolor="red",label="$20",style=dashed];
--> 0[fontcolor="red",label="$75",style=dashed];
--> 2[fontcolor="red",label="$10",style=dashed];
--> 3[fontcolor="red",label="$65",style=dashed];
-−
-</graphviz>
-−
-−
-−
-−
-−
-−
-[[Category:Алгоритмы]]
-−
-{{replicate-from-custiswiki-to-lib}}