Алгоритм Дейкстры – алгоритм на графах, который находит кратчайший путь между двумя данными вершинами в графе с неотрицательными длинами дуг. Также часто ставится задача расчёта кратчайшего пути от данной вершины до всех остальных. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации.

Описание

На вход алгоритма подаётся взвешенный ориентированный граф с дугами неотрицательного веса. На выходе получается набор кратчайших путей от данной вершины до других.

В начале расстояние для начальной вершины полагается равным нулю, а расстояния до всех остальных понимаются бесконечными. Массив флагов, обозначающих то, пройдена ли вершина, заполняется нулями. Затем на каждом шаге цикла ищется вершина с минимальным расстоянием до изначальной и флагом равным нулю. Для неё устанавливается флаг и проверяются все соседние вершины. Если рассчитанное ранее расстояние от исходной вершины до проверяемой больше, чем сумма расстояния до текущей вершины и длины ребра от неё до проверяемой вершины, то расстояние до проверяемой вершины приравниваем к расстоянию до текущей+ребро от текущей до проверяемой. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда расстояние до всех вершин c флагом 0 бесконечно. Последний случай возможен тогда и только тогда, когда граф несвязеный.

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

Вход: С : array of real – матрица длин дуг графа; s – вершина, от которой ищется кратчайший путь и t – вершина, к которой он ищется.

Выход: векторы Т: array of real; и Н: array of 0..р. Если вершина v лежит на кратчайшем пути от s к t, то T[v] - длина кратчайшего пути от s к у; Н[у] - вершина, непосредственно предшествующая у на кратчайшем пути.

Н – массив, в котором вершине n соответствует вершина m, предыдущая на пути к n от s.

T – массив, в котором вершине n соответствует расстояние от неё до s.

X – массив, в котором вершине n соответствует 1, если путь до неё известен, и 0, если нет.

инициализация массивов:

for v from 1 to р do

Т[ v ]: = ∞ { кратчайший путь неизвестен }

X[v]: = 0 { все вершины не отмечены}

H[s]: = 0 { s ничего не предшествует }

T[s] : = 0 { кратчайший путь имеет длину 0...}

X[s] : = 1 { ...и он известен } v : = s { текущая вершина }

М: { обновление пометок }

for и ∈ Г(и ) do

if Х[и] = 0 & Т[и] > T[v] + C then

Т[и] : = T[v] + C { найден более короткий путь из s в и через v }

H[u]: = v { запоминаем его }

m : = ∞

v : = 0

{ поиск конца кратчайшего пути }

for и from 1 to p do

if X[u] = 0 &T[u] < t then

v: = u ;

m: = T[u] { вершина v заканчивает кратчайший путь из s

if v = 0 then

stop { нет пути из s в t } end if

if v = t then

stop { найден кратчайший путь из s в t } end if

X[v]: = 1 { найден кратчайший путь из s в v } goto M

Обоснование

Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М, в качестве v используется вершина, для которой известен кратчайший путь из вершины s. Другими словами, если X[v] = 1, то T[v] = d(s,v), и все вершины на пути (s,v), определяемом вектором Н, обладают тем же свойством, то есть

Vu Т[и] = 1 => Т[и] = d(s,u)&T] = 1.

Действительно (по индукции), первый раз в качестве v используется вершина s, для которой кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны). Пусть Т[u] = d(s,u) для всех ранее помеченных вершин и. Рассмотрим вновь помеченную вершину v , которая выбрана из условия T[v] = min Т[и]. Заметим, что если известен путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что T[v]> d(s, v), то есть найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую что T[w]= 0.Имеем: T[w]= d(s,w)⩽d(s>v) < Т[v],что противоречит выбору вершины u.

Временная сложность

Сложность алгоритма Дейкстры зависит от способа нахождения не посещённой вершины с минимальным расстоянием до изначальной, способа хранения множества непосещённых вершин и способа обновления меток. Пусть n количество вершин, а через m - количество рёбер в графе. Тогда в простейшем случае, когда для поиска вершины с минимальным расстоянием до изначальной вершины просматривается всё множество вершин, а для хранения расстояний используется массив, время работы алгоритма - О(n 2). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма O(n 2 +m), но, так как m много меньше n(n-1), в конечном счёте получается О(n 2).

Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения расстояний. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, время работы такой реализации - О(nlogn+mlogn)

Пример

Вычисление расстояний от вершины 1 по проходимым вершинам:

Рассмотрим пример нахождение кратчайшего пути. Дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.

Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.


Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

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

Второй шаг

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Вершина 1 уже посещена. Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется.


Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22<10000, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, помечаем её как посещенную.

Третий шаг

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.

Четвертый шаг

Пятый шаг

Шестой шаг

Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 — 3 — 6 — 5 , поскольку таким путем мы набираем минимальный вес, равный 20.

Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5 ), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины.
Так, вершина 5 имеет длину пути 20 . Она связана с вершинами 6 и 4 .
Для вершины 6 получим вес 20 — 9 = 11 (совпал) .
Для вершины 4 получим вес 20 — 6 = 14 (не совпал) .
Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6 ), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути.
Далее определяем ребро, через которое мы попали в вершину 6 . И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.

Реализация алгоритма Дейкстры

Для хранения весов графа используется квадратная матрица. В заголовках строк и столбцов находятся вершины графа. А веса дуг графа размещаются во внутренних ячейках таблицы. Граф не содержит петель, поэтому на главной диагонали матрицы содержатся нулевые значения.

	1	2	3	4	5	6
1	0	7	9	0	0	14
2	7	0	10	15	0	0
3	9	10	0	11	0	2
4	0	15	11	0	6	0
5	0	0	0	6	0	9
6	14	0	2	0	9	0

Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 6
int main()
{
int a; // матрица связей
int d; // минимальное расстояние
int v; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251" );
system("cls" );
// Инициализация матрицы связей
for (int i = 0; i {
a[i][i] = 0;
for (int j = i + 1; j printf("Введите расстояние %d - %d: " , i + 1, j + 1);
scanf("%d" , &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Вывод матрицы связей
for (int i = 0; i {
for (int j = 0; j printf("%5d " , a[i][j]);
printf("\n" );
}
//Инициализация вершин и расстояний
for (int i = 0; i {
d[i] = 10000;
v[i] = 1;
}
d = 0;
// Шаг алгоритма
do {
minindex = 10000;
min = 10000;
for (int i = 0; i { // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i] { // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000)
{
for (int i = 0; i {
if (a[i] > 0)
{
temp = min + a[i];
if (temp < d[i])
{
d[i] = temp;
}
}
}
v = 0;
}
} while (minindex < 10000);
// Вывод кратчайших расстояний до вершин
printf("\nКратчайшие расстояния до вершин: \n" );
for (int i = 0; i printf("%5d " , d[i]);

// Восстановление пути
int ver; // массив посещенных вершин
int end = 4; // индекс конечной вершины = 5 - 1
ver = end + 1; // начальный элемент - конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d; // вес конечной вершины

while (end != begin_index) // пока не дошли до начальной вершины
{
for (int i = 0; i// просматриваем все вершины
if (a[i] != 0) // если связь есть
{
int temp = weight - a[i]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf("\nВывод кратчайшего пути\n" );
for (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
return 0;
}

Результат выполнения


Назад:

Дан ориентированный или неориентированный взвешенный граф с вершинами и рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина . Требуется найти длины кратчайших путей из вершины во все остальные вершины, а также предоставить способ вывода самих кратчайших путей.

Эта задача называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).

Алгоритм

Здесь описывается алгоритм, который предложил голландский исследователь Дейкстра (Dijkstra) в 1959 г.

Заведём массив , в котором для каждой вершины будем хранить текущую длину кратчайшего пути из в . Изначально , а для всех остальных вершин эта длина равна бесконечности (при реализации на компьютере обычно в качестве бесконечности выбирают просто достаточно большое число, заведомо большее возможной длины пути):

Кроме того, для каждой вершины будем хранить, помечена она ещё или нет, т.е. заведём булевский массив . Изначально все вершины не помечены, т.е.

Сам алгоритм Дейкстры состоит из итераций . На очередной итерации выбирается вершина с наименьшей величиной среди ещё не помеченных, т.е.:

(Понятно, что на первой итерации выбрана будет стартовая вершина .)

Выбранная таким образом вершина отмечается помеченной. Далее, на текущей итерации, из вершины производятся релаксации : просматриваются все рёбра , исходящие из вершины , и для каждой такой вершины алгоритм пытается улучшить значение . Пусть длина текущего ребра равна , тогда в виде кода релаксация выглядит как:

На этом текущая итерация заканчивается, алгоритм переходит к следующей итерации (снова выбирается вершина с наименьшей величиной , из неё производятся релаксации, и т.д.). При этом в конце концов, после итераций, все вершины графа станут помеченными, и алгоритм свою работу завершает. Утверждается, что найденные значения и есть искомые длины кратчайших путей из в .

Стоит заметить, что, если не все вершины графа достижимы из вершины , то значения для них так и останутся бесконечными. Понятно, что несколько последних итераций алгоритма будут как раз выбирать эти вершины, но никакой полезной работы производить эти итерации не будут (поскольку бесконечное расстояние не сможет прорелаксировать другие, даже тоже бесконечные расстояния). Поэтому алгоритм можно сразу останавливать, как только в качестве выбранной вершины берётся вершина с бесконечным расстоянием.

Восстановление путей . Разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из до любой вершины. Для этого достаточно так называемого массива предков : массива , в котором для каждой вершины хранится номер вершины , являющейся предпоследней в кратчайшем пути до вершины . Здесь используется тот факт, что если мы возьмём кратчайший путь до какой-то вершины , а затем удалим из этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной , и этот путь будет кратчайшим для вершины . Итак, если мы будем обладать этим массивом предков, то кратчайший путь можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в стартовую вершину — так мы получим искомый кратчайший путь, но записанный в обратном порядке. Итак, кратчайший путь до вершины равен:

Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины происходит улучшение расстояния до некоторой вершины , мы записываем, что предком вершины является вершина :

Доказательство

Основное утверждение , на котором основана корректность алгоритма Дейкстры, следующее. Утверждается, что после того как какая-либо вершина становится помеченной, текущее расстояние до неё уже является кратчайшим, и, соответственно, больше меняться не будет.

Доказательство будем производить по индукции. Для первой итерации справедливость его очевидна — для вершины имеем , что и является длиной кратчайшего пути до неё. Пусть теперь это утверждение выполнено для всех предыдущих итераций, т.е. всех уже помеченных вершин; докажем, что оно не нарушается после выполнения текущей итерации. Пусть — вершина, выбранная на текущей итерации, т.е. вершина, которую алгоритм собирается пометить. Докажем, что действительно равно длине кратчайшего пути до неё (обозначим эту длину через ).

Рассмотрим кратчайший путь до вершины . Понятно, этот путь можно разбить на два пути: , состоящий только из помеченных вершин (как минимум стартовая вершина будет в этом пути), и остальная часть пути (она тоже может включать помеченные вершины, но начинается обязательно с непомеченной). Обозначим через первую вершину пути , а через — последнюю вершины пути .

Докажем сначала наше утверждение для вершины , т.е. докажем равенство . Однако это практически очевидно: ведь на одной из предыдущих итераций мы выбирали вершину и выполняли релаксацию из неё. Поскольку (в силу самого выбора вершины ) кратчайший путь до равен кратчайшему пути до плюс ребро , то при выполнении релаксации из величина действительно установится в требуемое значение.

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

С другой стороны, поскольку и , и — вершины непомеченные, то так как на текущей итерации была выбрана именно вершина , а не вершина , то получаем другое неравенство:

Из этих двух неравенств заключаем равенство , а тогда из найденных до этого соотношений получаем и:

что и требовалось доказать.

Реализация

Итак, алгоритм Дейкстры представляет собой итераций, на каждой из которых выбирается непомеченная вершина с наименьшей величиной , эта вершина помечается, и затем просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра делается попытка улучшить значение на другом конце ребра.

Время работы алгоритма складывается из:

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

Реализация :

const int INF = 1000000000 ; int main() { int n; ... чтение n ... vector < vector < pair< int ,int > > > g (n) ; ... чтение графа... int s = ...; // стартовая вершина vector< int > d (n, INF) , p (n) ; d[ s] = 0 ; vector< char > u (n) ; for (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }

Здесь граф хранится в виде списков смежности: для каждой вершины список содержит список рёбер, исходящих из этой вершины, т.е. список пар >, где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.

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

Пусть задан орграф G (V , E ), каждой дуге которого поставлено в соответствие число
, называемое длиной дуги .

Определение. Длиной пути называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем пути ставится так.

Вариант 1. Найти длины кратчайших путей (путей минимальной длины) и сами пути от фиксированной вершины s до всех остальных вершин графа.

Вариант 2. Найти длины кратчайших путей и сами пути между всеми парами вершин данного графа.

Если в графе имеются дуги отрицательной длины, задача может не иметь решений (потеряет смысл). Это происходит из-за того, что в графе может присутствовать контур отрицательной длины. Наличие контуров отрицательной длины означает, что длину пути можно сделать равной
. А если контуров отрицательной длины нет, то кратчайшие пути существуют и любой кратчайший путь – это простая цепь.

Заметим, что если кратчайший путь существует, то любой его подпуть – это тоже кратчайший путь между соответствующими вершинами.

Алгоритм Дейкстры решения задачи о кратчайшем пути.

Алгоритм работает с дугами положительной длины и определяет кратчайшие пути от фиксированной вершины s до всех остальных вершин графа. Обозначим эти вершины v 1 , v 2 ,…, v n .

Определение. Назовем вершину u лежащей ближе к вершине s , чем вершина v , если длина кратчайшего пути от s до u меньше длины кратчайшего пути от s до v . Будем говорить, что вершины u и v равноудалены от вершины s , если длины кратчайших путей от s до u и от s до v совпадают.

Алгоритм Дейкстры последовательно упорядочивает вершины графа в смысле близости к вершине s и основан на следующих базовых принципах.

Если длины дуг – положительные числа, то

ближайшая к s вершина – она сама. Длина кратчайшего пути от s до s равна 0;

ближайшая к s вершина, отличная от s , лежит от s на расстоянии одной дуги  самой короткой из всех дуг, выходящих из вершины s ;

любая промежуточная вершина кратчайшего пути от s до некоторой вершины v лежит ближе к s , чем конечная вершина v ;

кратчайший путь до очередной упорядоченной вершины может проходить только через уже упорядоченные вершины.

Пусть алгоритм уже упорядочил вершины v 1 , v 2 … v k . Обозначим через
,
длину кратчайшего пути до вершины v i .

Рассмотрим все дуги исходного графа, которые начинаются в одной из вершин множества
и оканчиваются в еще неупорядоченных вершинах. Для каждой такой дуги, например
, вычислим сумму
. Эта сумма равна длине пути из s в y , в котором вершина v i есть предпоследняя вершина, а путь из s в v i – кратчайший из всех путей, соединяющих s и v i .

Этим самым определены длины всех путей из s в еще не упорядоченные вершины, в которых промежуточными вершинами являются только вершины из числа k ближайших к s . Пусть кратчайший из этих путей оканчивается на вершине w . Тогда w и есть
по близости к s вершина.

Технически действия по алгоритму Дейкстры осуществляются при помощи аппарата меток вершин. Метка вершины v обозначается как
. Всякая метка – это число, равное длине некоторого пути от s до v . Метки делятся на временные и постоянные. На каждом шаге только одна метка становиться постоянной. Это означает, что ее значение равно длине кратчайшего пути до соответствующей вершины, а сама эта вершина упорядочивается. Номер очередной упорядоченной вершины обозначим буквой р .

Описание алгоритма .

Шаг 1. (Начальная установка) . Положить
и считать эту метку постоянной. Положить
,
и считать эти метки временными. Положить
.

Шаг 2. (Общий шаг). Он повторяется n раз, пока не будут упорядочены все вершины графа.

Пересчитать временную метку
всякой неупорядоченной вершины v i , в которую входит дуга, выходящая из вершины р, по правилу

Выбрать вершину с минимальной временной меткой. Если таких вершин несколько, выбрать любую.

Пусть w - вершина с минимальной временной меткой. Считать метку
постоянной и положить
.

Шаги алгоритма Дейкстры удобно оформлять в таблице, каждый столбец которой соответствует вершине графа. Строки таблицы соответствуют повторению общего шага.

Пример . Для графа на рис. 4. найти кратчайшие пути от вершин
до всех остальных вершин графа. Ребра означают две разнонаправленные дуги одинаковой длины.

Решение. В табл. 1 записаны метки вершин на каждом шаге. Постоянные метки помечены знаком «+». Подробно опишем, как вычисляются метки вершин.

Из вершины 1 выходят дуги в вершины 2, 5, 6. Пересчитываем метки этих вершин и заполним вторую строку таблицы.

Метка вершины 6 становиться постоянной,
.

Из вершины 6 выходят дуги в еще неупорядоченные вершины 2, 5, 8, 9. Пересчитываем их временные метки

Заполняем 3 строку таблицы. Минимальная из временных меток равна 3 (метка вершины 9),
.

Из вершины 9 выходят дуги в еще неупорядоченные вершины 5, 8, 11, 12. Тогда

Заполняем четвертую строку таблицы. В этой строке две вершины  2 и 12 имеют минимальные временные метки, равные 4. Сначала упорядочим, например, вершину 2. Тогда на следующем шаге будет упорядочена вершина 12.

Таблица 1

Итак,
.

Из вершины 2 выходят дуги в еще неупорядоченные вершины 3, 4, 5. Пересчитываем временные метки этих вершин

Заполняем 5 строку таблицы. Минимальная из временных меток равна 4 (метка вершины 12),
.

Заполняем 6 строку таблицы. Минимальная из временных меток равна 5 (метка вершины 5),
.

Заполняем 7 строку таблицы. Становиться постоянной метка вершины 8 (она равна 5),
.

Вершина 11 упорядочивается.

Из вершины 11 выходят дуги в неупорядоченные вершины 7, 10. Пересчитываем временные метки этих вершин

Вершина 4 получает постоянную метку.

Из вершины 4 выходят дуги в неупорядоченные вершины 3, 7. Пересчитываем временные метки

Упорядочиваем вершину 3.

Заполняем 12 строку таблицы. На этом шаге упорядочиваем последнюю неупорядоченную вершину 10.

Построение дерева кратчайших путей.

Дерево кратчайших путей – это ориентированное дерево с корнем в вершине S . Все пути в этом дереве – кратчайшие для данного графа.

Дерево кратчайших путей строится по таблице, в него включаются вершина за вершиной в том порядке, в котором они получали постоянные метки. Первым в дерево включается корень – вершина S .

Построим дерево кратчайших путей для нашего примера.

Сначала включаем в дерево корень – вершину 1. Затем в дерево включается дуга (1,6). Следующей была упорядочена вершина 9, длина кратчайшего пути до которой равна 3. Первый раз число 3 появилось в третьей строке, которая заполнялась при
. Следовательно, вершина 6 – предпоследняя вершина кратчайшего пути до вершины 9. Включаем в дерево дугу (6,9) длины 1.

Затем была упорядочена вершина 2 с длиной кратчайшего пути, равной 4. Это число первый раз появилось в третьей строке, которая заполнялась при
. Следовательно, кратчайший путь во вторую вершину проходит по дуге (6,2). Включаем в дерево дугу (6,2) длины 2.

Далее была упорядочена вершина 12,
. Первый раз число 4 появляется в четвертой строке, которая заполнялась при
. В дерево включается дуга (9,12) длины 1. Полное дерево кратчайших путей показано на рис. 5.

Алгоритм Дейкстры может ошибаться, если в графе есть дуги отрицательной длины. Так, отыскивая кратчайшие пути от вершины s =1 для графа на рис. 6, алгоритм сначала упорядочит вершину 3, затем вершину 2 и закончит работу. При этом этот кратчайший путь до вершины 3, с точки зрения алгоритма Дейкстры,  это дуга (1,3) длины 3.

На самом деле, кратчайший путь до вершины 3 состоит из дуг (1,2) и (2,3), длина этого пути равна 5+(-3)=2.

Из-за наличия дуги (2,3) отрицательной длины –3 оказались нарушенными следующие базовые принципы:

ближайшая к s вершина лежит от нее на расстоянии двух дуг, а не одной;

промежуточная вершина кратчайшего пути 1-2-3 (вершина 2) лежит дальше от вершины 1 (на расстоянии 5), чем конечная вершина пути 3.

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

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

Этот граф мы можем представить в виде матрицы С:

Возьмем в качестве источника вершину 1. Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5.
Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере.

Присвоим 1-й вершине метку равную 0, потому как эта вершина - источник. Остальным вершинам присвоим метки равные бесконечности.

Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников. Каждой из рассмотренных вершин назначим метку равную сумме метки W и длинны пути из W в рассматриваемую вершину, но только в том случае, если полученная сумма будет меньше предыдущего значения метки. Если же сумма не будет меньше, то оставляем предыдущую метку без изменений.

После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещённую, и выбираем из ещё не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W.

Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.

Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины.

Выполнив все действия получим такой результат:

Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {1, 1, 1, 1, 1}). Далее на этапе пересчета значения метки для рассматриваемой вершины, в случае если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у 3-ей вершины была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р - Р=5. Также при W=5 изменилось значение метки у 4-й вершины (было «50», стало «40»), значит нужно присвоить 4-му элементу вектора Р значение W - P=5. В результате получим вектор Р = {1, 1, 5, 5, 1}.

Зная что в каждом элементе вектора Р записана последняя промежуточная вершина на пути между источником и конечной вершиной, мы можем получить и сам кратчайший маршрут.