VitaliyFilippov: 1 версия

2009-03-27T10:04:42Z

1 версия

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

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

В этом алгоритме, для графа <m>G=(V,E)</m> последовательно выполняются <m>n=|V|</m> итераций, улучшая матрицу <m>D_{ij}</m> минимальных стоимостей пути из вершины ''i'' в вершину ''j'', с возможным использованием (для ''k''-той итерации) промежуточных вершин из множества <m>1,\dots,k</m>. Вычислять эту матрицу очень легко, изначально она определяется весовой функцией ребер, <m>D^0_{ij}=w_{ij}</m>, для тех ''i'' и ''j'', для которых есть ребро ''(i,j)'', и <m>+\infty</m> для остальных.
Обновление этой матрицы на ''k''-той итерации происходит по очевидной формуле:
<m>D^k_{ij}=min(D^{k-1}_{ij},D^{k-1}_{ik}+D^{k-1}_{kj})</m>, где <m>D^{k-1}</m> — значение этой матрицы на предыдущей итерации.
Таким образом, очевидна и корректность алгоритма, и его сложность, состовляющая <m>O(n^3)</m>.

<code-python>
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
</code-python>

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

===Входной граф===
<graph>
digraph G{ rankdir=LR;
node[fontsize=16];
edge[fontcolor=blue,style=dashed];
0 [label="NY(0)"];
1 [label="Moscow(1)"];
2 [label="Minsk(2)"];
3 [label="Berlin(3)"];
4 [label="Kiev(4)"];
0 -> 4[label="$80"];
1 -> 0[label="$60"];
3 -> 0[label="$50"];
1 -> 2[label="$-5"];
1 -> 3[label="$50"];
1 -> 4[label="$10"];
2 -> 1[label="$10"];
3 -> 1[label="$30"];
4 -> 1[label="$15"];
3 -> 2[label="$20"];
4 -> 2[label="$15"];
3 -> 4[label="$30"];
}
</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:Алгоритмы|Ф]]
{{replicate-from-custiswiki-to-lib}}

Алгоритм Флойда-Уоршолла - История изменений

VitaliyFilippov: 1 версия