|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Поиск кратчайших путей:алгоритм Флойда-УоршоллаМатериал из CustisWikiВерсия от 00:12, 21 июня 2006; AntMatrik (обсуждение | вклад) Алгоритм Флойда-Уоршолла (Floyd-Warshall) предназначен для решения задачи поиска кратчайших путей в графе — Shortest Path Problem. В отличие от алгоритма Дейкстры, он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми точками). В этом алгоритме, для графа последовательно выполняются итераций, улучшая матрицу минимальных стоимостей пути из вершины i в вершину j, с возможным использованием (для k-той итерации) промежуточных вершин из множества . Вычислять эту матрицу очень легко, изначально она определяется весовой функцией ребер, , для тех i и j, для которых есть ребро (i,j), и для остальных. Обновление этой матрицы на k-той итерации происходит по очевидной формуле: , где — значение этой матрицы на предыдущей итерации. Таким образом, очевидна и корректность алгоритма, и его сложность, состовляющая . # Находит стоимость кратчайшего пути для всех пар вершин. # Выбор и хранение самих оптимальных путей не показаны для простоты. 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 [[ 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,]]
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Поиск кратчайших путей:алгоритм Флойда-Уоршолла» |
![]() |
![]() |
![]() |