Лекции - Структуры и алгоритмы компьютерной обработки данных / 19.Нахождение кратчайших путей во взвешенном графе, алгоритмы Флойда и Дейкстры

Задача о кратчайших путях

1. Найти кратчайший пути из А в В.

2. Найти кратчайшие пути из А до остальных вершин.

3. Найти кратчайшие пути между всеми парами вершин.

Первая задача не проще второй, поэтому будем искать решение второй и третьей задачи.

Отрицательные веса

Ребра могут иметь отрицательный вес. Если существует цикл отрицательного веса, то задача не имеет решения.Пример: задача об обмене валют. Вершины графа - валюты, ребра – курсы обмена. После логарифмирования получаем отрицательные веса.

Ослабление пути

Алгоритмы поиска кратчайших путей основаны на операции ослабления пути.

Если D[i,j] > D[i.k]+D[k,j] то

D[i,j] := D[i.k]+D[k,j]

Кратчайшие пути от заданной вершины до остальных (неотрицательные веса)

Алгоритм Дейкстры. Задача – получить массив расстояний D[i]. Вершины обрабатываются по одной, начиная с начальной. На каждом шаге выбирается еще не обработанная вершина с минимальным расстоянием. После этого для остальных необработанных вершин выполняется ослабление через выбранную.

Процедура алгоритма Дейкстры

D[1..n] – массив расстояний; P[1..N] – номер предыдущей вершины в пути; V[1..N] – массив пометок.

//инициализация

V[1]:=true; for i:=2 to n do V[i]:=false;

for i:=1 to n do D[i]:=A[1,i];

for i:=1 to n do P[i]:=1;

//основной цикл

for i:=2 to n do

begin //поиск ближайшей вершины

min:=oo;

for i:=1 to n do

if not(V[i]) and (D[i]< min)

then begin min:=D[i]; m:=i end;

V[m]:=true; //обновление расстояний

for i:=1 to n

if not(V[i]) and (D[i] > A[m,i]+ D[m])

then begin D[i]:=A[m,i] + D[m]; P[i]:=m end;

end; //Сложность – O(n2)

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

Поиск кратчайших путей между всеми парами вершин. Матрица D[i,j] – длина кратчайшего пути, P[i,j] – предпоследняя вершина на пути из i в j.

D:=A;

for i:=1 to n do for j:=1 to n do P[i,j]:=i;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if D[i,j] > D[i,k]+D[k,j] then

begin

D[i,j] := D[i,k]+D[k,j]; P[i,j] := P[k,j]

end;

Сложность Ө(n3).

Задачи, решаемые с помощью алгоритма Флойда

• Обнаружение цикла отрицательного веса (признак: A[i,i] < 0)

• Поиск диаметра графа (максимального расстояния между вершинами)

• Поиск центра графа (вершины, для которой сумма расстояний до других вершин минимальна)

Задача о кратчайших путях. Другие алгоритмы

• В ациклическом графе можно сделать топологическую сортировку и перебрав вершины в этом порядке выполнить ослабление по исходящим ребрам (Ө(m)). Этот алгоритм адаптируется для поиска самого длинного пути.

• В графе с отрицательными весами можно найти путь от одной вершины до всех остальных, используя алгоритм Форда-Беллмана. Для этого n раз выполняем ослабление вдоль каждого ребра. (Ө(mn)).