Кратчайшие пути в графе

Определения
Пусть G = (V, E) – ориентированный граф. Поставим в соответствие каждому ребру e∈E в графе G неотрицательную стоимость c(e).
c: E → R+ - функция стоимости
Стоимость пути определяется как сумма стоимостей ребер, образующих его.
Задача о нахождении кратчайшего пути состоит в нахождении для каждой пары узлов (v, w) пути наименьшей стоимости.

Нахождение кратчайшего пути
из одного источника

Алгоритм Дейкстры
Идея алгоритма Дейкстры нахождения кратчайших путей из одной вершины во все другие состоит в следующем.
1. Строится множество S, содержащее вершины графа, кратчайшие расстояния до которых от источника известны.
2. На каждом шаге добавляется тот из оставшихся узлов, кратчайшее расстояние до которого меньше всех других оставшихся узлов.

Алгоритм Дейкстры
Вход:
G= (V, E) – ориентированный граф,
v0 ∈V – источник,
c : E →R+ – функция стоимости ребер графа G.
Полагаем , что
c(vi, vj ) = +∞, если (vi, vj ) ∉Е
c (v, v) = 0.
Выход:
для всех вершин v ∈ V наименьшая сумма стоимостей ребер из E, взятая по всем путям, идущим из v0 в v.

Алгоритм Дейкстры
Метод:
Строим такое множество S ⊆ V, что кратчайший путь из источника в каждый узел v ∈S целиком лежит в S.
Массив D[v] содержит стоимость текущего кратчайшего пути из v0 в v.

Алгоритм Дейкстры - O(n2)
{
S ← {v0};
D[v0] ← 0;
для всех v ∈V \ {v0} выполнить: D[v] = c (v0, v);
пока S ≠ V выполнять:
{
выбрать узел w ∈ V \ S, для которого
D[w] принимает наименьшее значение;
добавить w к S;
для всех v ∈V \ S выполнить
D[v] = min (D[v], D[w] + c(w, v));
}
}

Алгоритм Дейкстры. Пример
№ S w D[w] D[1] D[2] D[3] D[4]
0 {0} - - 2 +∞ +∞ 10
{0, 1} 1 2 2 5 +∞ 9
{0, 1, 2} 2 5 2 5 9 9
{0, 1, 2, 3} 3 9 2 5 9 9
4 {0, 1, 2, 3, 4} 4 9 2 5 9 9
0
2
1
4
3
2
3
4
5
10
7
6

Алгоритм Беллмана-Форда
Задача:
Для заданного взвешенного графа G=(V, E) найти кратчайшие пути из заданной вершины s до всех остальных вершин.
В случае, когда в графе G содержатся отрицательные циклы, достижимые из s, сообщить, что кратчайших путей не существует.

Алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда
bool FordBellman(s):
for v ∈ V
d[v] ← ∞
d[s] ← 0
for i ← 1 to |V|−1
for (u,v) ∈ E
if d[v] > d[u] + с(u,v) // с(u,v) — вес ребра uv
d[v] ← d[u] + с(u,v)
p[v] ← u //u – это предок v
for (u,v) ∈ E
if d[v] > d[u] + с(u,v)
return false // цикл отрицательного веса
return true

Алгоритм Беллмана-Форда. Пример
t
z
y
x
s
7
-3
-4
2
9
8
7
-2
5
6
0
∞
∞
∞
∞
6
-2
7
4
2
2

Алгоритм Беллмана-Форда
Оценка сложности алгоритма:
Инициализация занимает Θ(V) времени,
каждый из |V|−1 проходов требует Θ(E) времени,
обход по всем ребрам для проверки наличия отрицательного цикла занимает O(E) времени.
Значит, алгоритм Беллмана-Форда работает за O(VE) времени.

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

Алгоритм Флойда-Уоршолла
Пусть G= (V, E) – ориентированный граф,
c : E →R+ – функция стоимости ребер графа G.
Строим матрицу стоимостей:
c(i, j), если ребро (i, j)∈E
M[i, j] = +∞ , если ребро (i, j)∉E
0, если i = j
Обозначим через d [i, j] матрицу кратчайших путей между всеми вершинами.
Вершины занумеруем числами от 1 до n.

Алгоритм Флойда-Уоршолла
Обозначим через dij(k) стоимость кратчайшего пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}.
M[i, j] , если k = 0,
dij(k) =
min(dij(k-1) , dik(k-1) + dkj(k-1) ), если k≥1
D(n) содержит искомое решение

Алгоритм Флойда-Уоршолла
Floyd-Warshall(M, n)
{
D(0) ← M;
for k ← 1 to n do
for i ←1 to n do
for j ← 1 to n do
dij(k) ← min(dij(k-1), dik(k-1) + dkj(k-1) );
return D(n);
}

Транзитивное замыкание графа
Пусть G= (V, E) ориентированный граф.
Транзитивным замыканием графа G называется граф G′ = (V, E′ ) , в котором из вершины v в вершину w идет дуга ⇔ существует путь из вершины v в вершину w в графе G.
E′ :
(a, b)∈E & (b, c) ∈ E ⇒
(a, b)∈E′ & (b, c) ∈ E′ & (a, c) ∈ E′

Построение транзитивного замыкания графа. Пример
1
3
2
5
4
1
3
2
5
4

Построение транзитивного замыкания графа
Обозначим через tij(k) наличие пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}. M – матрица смежности графа G.
M[i, j] , если k = 0,
tij(k) =
tij(k-1) ∨ (tik(k-1) ∧ tkj(k-1) ), если k≥1
T(n) содержит искомое решение.