Топологическая сортировка, пути в графе

Топологическая сортировка

Определение. Частичным порядком на множестве А называется отношение R, определенное

Примеры частичного порядка:
решение большой задачи разбивается на ряд подзадач, над которыми

Если R — частичный порядок на множестве А, то (А, R)

Определение. Линейный порядок R на множестве А — это такой частичный

Если задан частичный порядок R на множестве А, часто бывает нужен

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

Топологическая сортировка. Пример

Алгоритм. Топологическая сортировка

Вход. Частичный порядок R на конечном множестве А.
Выход. Линейный

Топологическая сортировка. Пример

1

2

3

4

5

6

7

8

9

Топологическая сортировка. Реализация на матрице смежности

1

2

3

4

5

6

7

8

9

Найти вершину, в которую не входит

Топологическая сортировка. Реализация на иерархических списках

1< 2;
3< 1;
4<1;
2< 5;
2< 6;

1

2

3

4

5

6

Топологическая сортировка. Реализация на иерархических списках

2

1

Ключ – номер вершины
Счетчик – количество

Работа алгоритма(построение)

1

2

2

1

5

1

4

0

6

1

3

0

Ключ
Счетчик
Следующий
Потомок

1

0

0

0

0

NUL

1< 2;
2< 5;
4 < 1;
2 < 6;
3 < 1;

NUL

NUL

NUL

NUL

NUL

NUL

Работа алгоритма (перестройка списка)

1

2

2

1

5

1

4

0

6

1

3

0

Ключ
Счетчик
Следующий
Потомок

1

0

0

0

0

NUL

NUL

NUL

NUL

NUL

NUL

Head

NUL

NUL

NUL

NUL

NUL

NUL

Кратчайшие пути

Пусть G = (V, E) – ориентированный граф. Поставим в

Ребра отрицательного веса

Веса ребер могут ребер могут быть отрицательными.
Важно знать, имеются

Пусть G = (V, E) – заданный граф.
Для каждой вершины

Идея алгоритма нахождения кратчайших путей
из одной вершины во все другие
Строится

Кратчайшие пути из вершины 10:

10

Техника релаксации

Для каждого ребра (u,v) храним d[v] – верхнюю оценку
кратчайшего пути

Релаксация ребра (u,v):
значение d[v] уменьшается до d[v+w(u,v)]
(если второе значение

Релаксация ребра при поиске кратчайших путей.

10

2

3

6

1

8

5

7

4

9

1

1

1

2

2

2

3

4

3

3

4

4

5

5

5

Пусть уже найдены оценки кратчайших путей для

В ходе работы алгоритма поддерживается множество S,
состоящее из вершин, для которых

Алгоритм Дейкстры

Dijkstra(G,w,s){
Initialize(G,s);
S ← ø;
Q ← V; //очередь с приоритетами
While (Q ≠

Пример. Каждой вершине из V сопоставили метку — минимальное известное расстояние

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины —
3-й

Все соседи вершины 1 проверены. Текущее минимальное расстояние до
вершины 1

Снова пытаемся уменьшить расстояния у смежных вершин, пытаясь
пройти в них через

Все смежные вершины с вершиной 2 просмотрены, замораживаем расстояние
до неё и

Повторяем шаг алгоритма для оставшихся вершин 6, 4 и 5.

Пример.

Очередь с приоритетами. Приоритет – текущая величина найденного расстояния
от начальной

Реализация с дополнительным массивом - O(n2)

Массив D[v] содержит стоимость текущего

Dijkstra
{
S ← {s};
D[s] ← 0;
для всех v ∈V \ {v0} выполнить:

Пример

№ S u D[u] 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

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также

* Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой

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

За время O(n × m) алгоритм находит кратчайшие

Идея алгоритма
Алгоритм позволяет очень просто определить, существует ли
в графе G отрицательный

Bellman-Ford(G,w,s) {
Initialize(G,s);
for(i=1; i for(∀ (u,v) ∈ E )
Relax(u,v,w);
for(∀ (u,v)

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

Если в ориентированном графе нет дуг с

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

Строим матрицу стоимостей:
w(i, j), если

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

Обозначим через dij(k) стоимость кратчайшего пути из вершины с номером

Floyd-Warshall(M, n) {
D(0) ← M;
for k ← 1 to n do

Транзитивное замыкание графа

Пусть G= (V, E) ориентированный граф. Транзитивным замыканием графа

Построение транзитивного замыкания графа. Пример

1

3

2

5

4

1

3

2

5

4

Обозначим через tij(k) наличие пути из вершины с номером i в

Алгоритм построения транзитивного замыкания графа

Tranzitive_Closure(M, n)
{
T(0) ← M;
for k ← 1

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

Если в ориентированном графе нет циклов, то