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

-     CUSTIS
    
    
     
     
    
    
     
     
      Сайт CUSTIS →
     
    
    
     
     
    
    
     
     
      Вакансии
     
    
    
     
     
    
    
     
     
      Блог команды
     
    
    
     
     
    
    
     
     
      Архив событий
     
    
    
     
     
    
    
     
     
      Архив публикаций
     
    
    
     
     
    
  
     
     Навигация
    
    
     
     
    
    
     
     
      Заглавная страница
     
    
    
     
     
    
    
     
     
      Свежие правки
     
    
    
     
     
    
    
     
     
      Случайная статья
     
    
    
     
     
    
    
     
     
      Справка
     
    
    
     
     
    
  
     
     Поиск
    
    
     
     
    
    
     
     
    
        
         
    


    
    
     
     
    
  
     
     Инструменты
    
    
     
     
    
    
     
     
      Ссылки сюда
     
    
    
     
     
    
    
     
     
      Связанные правки
     
    
    
     
     
    
    
     
     
      Спецстраницы
     
    
    
     
     
    
    
     
     
      Версия для печати
     
    
    
     
     
    

Чистый HTML



→M$WORD



→OOffice
+    Алгоритм Флойда-Уоршолла — различия между версиями
   
      
    Материал из CustisWiki
    
            Перейти к: навигация, поиск
    
    

				
				
				
				
				
				Версия 13:04, 27 марта 2009 (просмотреть исходный код)
VitaliyFilippov (обсуждение | вклад)
м (1 версия)
← Предыдущая правка
				Текущая версия на 20:45, 13 июня 2011 (просмотреть исходный код) 
StasFomin (обсуждение | вклад) 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
				
Строка 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
REDIRECT discopal:Алгоритм Флойда-Уоршолла







Источник — «http://lib.custis.ru/index.php?title=Алгоритм_Флойда-Уоршолла&oldid=27283»
 CUSTIS
       Сайт CUSTIS →
       Вакансии
       Блог команды
       Архив событий
       Архив публикаций
 Навигация
       Заглавная страница
       Свежие правки
       Случайная статья
       Справка
 Поиск
 Инструменты
       Ссылки сюда
       Связанные правки
       Спецстраницы
       Версия для печати
 Чистый HTML
 →M$WORD
 →OOffice
@@ Строка 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];
-[label="NY(0)"];
-[label="Moscow(1)"];
-[label="Minsk(2)"];
-[label="Berlin(3)"];
-[label="Kiev(4)"];
--> 4[label="$80"];
--> 0[label="$60"];
--> 0[label="$50"];
--> 2[label="$-5"];
--> 3[label="$50"];
--> 4[label="$10"];
--> 1[label="$10"];
--> 1[label="$30"];
--> 1[label="$15"];
--> 2[label="$20"];
--> 2[label="$15"];
--> 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}}