Персональные инструменты
 

Алгоритм Флойда-Уоршолла — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (1 версия)
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 1: Строка 1:
Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи
+
#REDIRECT [[discopal:{{PAGENAME}}]]
[[Поиск кратчайших путей в графе]]. В отличие от [[алгоритм Дейкстры|алгоритма Дейкстры]], он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми пунктами).
+
 
+
В этом алгоритме, для графа <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}}
+

Текущая версия на 20:45, 13 июня 2011

  1. REDIRECT discopal:Алгоритм Флойда-Уоршолла