[[Поиск кратчайших путей в графе]]. В отличие от [[алгоритм Дейкстры|алгоритма Дейкстры]], он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми пунктами).
[[Поиск кратчайших путей в графе]]. В отличие от [[алгоритм Дейкстры|алгоритма Дейкстры]], он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми пунктами).
−
В этом алгоритме, для графа <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> для остальных.
+
В этом алгоритме, для графа <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''-той итерации происходит по очевидной формуле:
Обновление этой матрицы на ''k''-той итерации происходит по очевидной формуле:
−
<math>D^k_{ij}=min(D^{k-1}_{ij},D^{k-1}_{ik}+D^{k-1}_{kj})</math>, где <math>D^{k-1}</math> — значение этой матрицы на предыдущей итерации.
+
<m>D^k_{ij}=min(D^{k-1}_{ij},D^{k-1}_{ik}+D^{k-1}_{kj})</m>, где <m>D^{k-1}</m> — значение этой матрицы на предыдущей итерации.
−
Таким образом, очевидна и корректность алгоритма, и его сложность, состовляющая <math>O(n^3)</math>.
+
Таким образом, очевидна и корректность алгоритма, и его сложность, состовляющая <m>O(n^3)</m>.
<code-python>
<code-python>
Версия 18:34, 22 октября 2008
Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи
Поиск кратчайших путей в графе. В отличие от алгоритма Дейкстры, он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми пунктами).
В этом алгоритме, для графа последовательно выполняются итераций, улучшая матрицу минимальных стоимостей пути из вершины i в вершину j, с возможным использованием (для k-той итерации) промежуточных вершин из множества . Вычислять эту матрицу очень легко, изначально она определяется весовой функцией ребер, , для тех i и j, для которых есть ребро (i,j), и для остальных.
Обновление этой матрицы на k-той итерации происходит по очевидной формуле:
, где — значение этой матрицы на предыдущей итерации.
Таким образом, очевидна и корректность алгоритма, и его сложность, состовляющая .
def floyd_warshal(D):
N=D.shape[0]
print_frame(D)for k inxrange(N):
#Сохраняем $D_{k-1}$ в $D_{old}$
D_old=array(D)for v1 inxrange(N):
for v2 inxrange(N):
D[v1,v2]=min( D[v1,v2], D_old[v1,k]+D_old[k,v2])
print_frame(D,D_old,k)return D
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
