Поиск по базе сайта:
Алгоритм Флойда Уоршелла Алгоритм Флойда Уоршелла icon

Алгоритм Флойда Уоршелла Алгоритм Флойда Уоршелла




Скачати 42.13 Kb.
НазваАлгоритм Флойда Уоршелла Алгоритм Флойда Уоршелла
Дата конвертації26.06.2013
Розмір42.13 Kb.
ТипДокументи

Алгоритм Флойда - Уоршелла

Алгоритм Флойда - Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

Более строгая формулировка этой задачи следующая: 
есть ориентированный граф G = (V, Е) каждой дуге v -> w этого графа сопоставлена неотрицательная стоимость C[v, w]. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин v, w) любого пути от вершины v в вершины w, длина которого минимальна среди всех возможных путей от v к w.

^ Формальное описание     

Для определенности положим, что вершины графа последовательно пронумерованы от 1 до n. Алгоритм Флойда использует матрицу А размера п * n, в которой вычисляются длины кратчайших путей. Вначале A[i, j] = C[i, j] для всех i != j. Если дуга i -» j отсутствует, то C[i, j] = infinity. Каждый диагональный элемент матрицы А равен 0.

Над матрицей А выполняется п итераций. После k-й итерации A[i, j] содержит значение наименьшей длины путей из вершины i в вершину у, которые не проходят через вершины с номером, большим k. Другими словами, между концевыми вершинами пути i и у могут находиться только вершины, номера которых меньше или равны k. На k-й итерации для вычисления матрицы А применяется следующая формула: 
Ak[i,j]=min(Ak-1[i,j], Ak-1[i,k]+Ak-1[k,j])

Нижний индекс k обозначает значение матрицы А после k-й итерации, но это не означает, что существует п различных матриц, этот индекс используется для сокращения записи. Для вычисления Ak[i, j] проводится сравнение величины Ak-i[i, j] (т.е. стоимость пути от вершины i к вершине j без участия вершины k или другой вершины с более высоким номером) с величиной Ak-1[i, k] + Ak-1[k, j] (стоимость пути от вершины i до вершины k плюс стоимость пути от вершины k до вершины j). Если путь через вершину k дешевле, чем Ak-1[i, j], то величина Ak[i, j] изменяется.

^ Оценка сложности     

Время выполнения этой программы, очевидно, имеет порядок 0(V3), поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов. Доказательство "правильности" работы этого алгоритма также очевидно и выполняется с помощью математической индукции по k, показывая, что на k-й итерации вершина k включается в путь только тогда, когда новый путь короче старого.

Пример     

Визуализатор для алгоритма Флойда - Уоршелла.


Пример графа и таблица расстояний для него

 















12 



-- 

22 







11 

--

10



14

7

0

--

17



19

12

5

0

4



15

8

1

--

0



^ Поиск кратчайшего пути во взвешенном графе\ Алгоритм Флойда-Уоршелла

   Дан ориентированный граф G= с матрицей смежности. Найти кратчайшее расстояние между всеми парами вершин.

Алгоритм Флойда-Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

Идея алгоритма сложна в понимании, но легка в реализации, что делает ее очень удобной при решении задач с маленькими ограничениями на размер графа (до 500 вершин).

В результате работы алгоритма мы должны получить матрицу кратчайших путей D:array[1..n, 1..n], в которой D[i,j] – кратчайшее расстояние от вершины с номером i до вершины с номером j.

Обозначим матрицу кратчайших путей, содержащих в качестве промежуточных вершины из подмножества [1 . .m] множества V через Dm. Тогда справедливо следующее:



Действительно, если кратчайшее расстояние от i до j содержит вершину m+1, то его можно разбить на 2 части: от i до (m+1)  и (m+1) до  j, а дальше вычислять по рекуррентной формуле.

Отметим, что D0 = mass, то есть изначально кратчайшие расстояния соответствуют матрице смежности.

Для вывода кратчайшего пути будем использовать тот же принцип «предков», только размерность массива «предков» будет соответствовать размерности D (что справедливо и для прошлых случаев). В целом техника запоминания предков остается та же.

Пример.



На рисунке приведен граф и часть трассировки программы:




Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації