Решить задачу о нахождении кратчайшего пути алгоритмом Дейкстры.
Найти кратчайший путь от Х0 до Х7. Граф задан элементами стоимостной матрицы
Построим этот граф
Начнем с элемента Х0 и присвоим ему метку 0, рассмотрим всех его соседей, т.к. там еще нет пометок, то присвоим им соответствующие длины:
Все соседи Х0 рассмотрены, помечаем ее и переходим к вершине Х1. ЕЕ соседи Х0, Х2,Х4, но Х0 помечена, не рассматриваем ее. Для Х2: 
, оставляем метку.
Для Х4: 
, заменяем метку. Все соседи вершины Х1 рассмотрены, помечаем ее
переходим к вершине Х2. ЕЕ соседи Х0, Х1,Х3, Х4, Х5, Х6, но Х0, Х1 помечены, не рассматриваем их.
Для Х3: 
, оставляем метку.
Для Х5: 
, заменяем метку.
Для Х4: 
, оставляем метку.
Для Х6: 
, заменяем метку.
Все соседи вершины Х2 рассмотрены, помечаем ее.
переходим к вершине Х3. ЕЕ соседи Х0, Х2, Х6, но Х0, Х2 помечены, не рассматриваем их.
Для Х6: 
, оставляем метку.
Все соседи вершины Х3 рассмотрены, помечаем ее.
переходим к вершине Х4. ЕЕ соседи Х1,Х2, Х5, Х7, но Х1, Х2 помечены, не рассматриваем их.
Для Х5: 
, заменяем метку.
Для Х7: 
, заменяем метку.
Все соседи вершины Х4 рассмотрены, помечаем ее.
переходим к вершине Х5. ЕЕ соседи Х2,Х4, Х6, Х7, но Х2, Х4 помечены, не рассматриваем их.
Для Х6: 
, оставляем метку.
Для Х7: 
, оставляем метку.
Все соседи вершины Х5 рассмотрены, помечаем ее.
переходим к вершине Х6. ЕЕ соседи Х2,Х3, Х5, Х7, но Х2, Х3, Х5 помечены, не рассматриваем их.
Для Х7: 
, оставляем метку.
Все соседи вершины Х6 рассмотрены, помечаем ее. И помечаем оставшуюся Х7, все вершины рассмотрены.
Вывод: Кратчайший путь их Х0 в Х7 имеет длину 101, этот путь: Х7-Х4-Х1-Х0.
Рассмотрим пример нахождение кратчайшего пути. Дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.
Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 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
scanf("%d"
, &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Вывод матрицы связей
for
(int
i = 0; i
for
(int
j = 0; 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
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
// Восстановление пути
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;
}
Результат выполнения
Назад:
Алгоритм Дейкстры предназначен для нахождения кратчайшего пути между вершинами в неориентированном графе.
Идея алгоритма следующая: сначала выберем путь до начальной вершины равным нулю и заносим эту вершину во множество уже выбранных, расстояние от которых до оставшихся невыбранных вершин определено. На каждом следующем этапе находим следующую выбранную вершину, расстояние до которой наименьшее, и соединенную ребром с какой-нибудь вершиной из множества невыбранных (это расстояние будет равно расстоянию до выбранной вершины плюс длина ребра).
Пример 1. Найти кратчайший путь на графе от вершины L до вершины D (рис. 10.7).
Рис. 10.7.
Запишем алгоритм в виде последовательности шагов (табл. 10.1). Шаг 1. Определяем расстояния от начальной вершины L до всех остальных.
Таблица 10.1
Метод Дейкстры (первый шаг)
|
Выбранная |
Путь до выбранной вершины |
Невыбранная вершина |
|||||||
Шаг 2. Выбираем наименьшее расстояние от L до В; найденная вершина В принимается за вновь выбранную. Найденное наименьшее расстояние добавляем к длинам ребер от новой вершины В до всех остальных. Выбираем минимальное расстояние от В до N. Новую вершину N принимаем за выбранную (табл. 10.2).
Таблица 10.2
Метод Дейкстры (второй шаг)
|
Выбранная |
Путь до выбранной вершины |
Невыбранная вершина |
|||||||
Для наглядности в дальнейшем вместо знака оо будем ставить знак « - ».
Шаг 3. Определяем расстояния от вершины N л о всех оставшихся (за исключением L и В), как показано в табл. 10.3.
Таблица 10.3
Метод Дейкстры (третий шаг)
|
Выбранная |
Путь до выбранной вершины |
Невыбранная вершина |
|||||||
Расстояние от вершины L через вершину N до вершины G равно 18 условных единиц. Это расстояние больше, чем расстояние LB + BG = 16 условных единиц, вследствие чего оно не учитывается в дальнейшем. Продолжая аналогичные построения, составим табл. 10.4. Таким образом, найдена длина кратчайшего пути между вершинами L и D (44 условных единицы).
Траекторию пути определяем следующим образом. Выполняем обратный просмотр от конечной вершины к начальной. Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. В столбце, соответствующем вершине D, впервые минимальная длина 44 условных единицы появилась снизу в четвертой строке. В этой строке указана вершина S, к которой следует перейти, т.е. следующим нужно рассматривать столбец, соответствующий вершине S.
Таблица 10.4
|
Выбранная вершина |
Путь до выбранной вершины |
Невыбранная вершина |
|||||||
В этом столбце минимальная длина, равная 27 условным единицам, указывает следующую вершину G, к которой надлежит перейти, и т.д. Таким образом, получаем траекторию пути: (L, В, G, S, D).
Пример 8. Найти кратчайший путь на графе между 1-й и 7-й вершинами (рис. 10.8).
Определяем (табл. 10.5) следующую выбранную вершину, расстояние до которой наименьшее и соединенную ребром с одной из вершин, принадлежащих множеству невыбранных (это расстояние будет равно расстоянию до выбранной вершины плюс длина ребра).
Рис. 10.8. Граф (а) и соответствующая ему матрица смежности (б)
Табличная реализация метода Дейкстры
Таблица 10.5
|
Выбранная |
Путь до выбранной вершины |
Невыбранная вершина |
||||||
|
у 6 |
||||||||
Выполняем обратный просмотр от конечной вершины к начальной.
Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. Кратчайший путь при этом будет равен (V 7 - V 5 - V 2 - У {).
и КОНТРОЛЬНЫЕ ВОПРОСЫ
- 1. Какова теоретическая сложность алгоритмов: построения дерева решений, динамического программирования и Дейкстры?
- 2. В чем особенность использования дерева решений для ориентированного и неорентированного графа?
- 3. В решении каких прикладных задач используются алгоритмы определения в графе кратчайших расстояний между заданными вершинами?
- 4. Может ли быть применен рассмотренный в работе алгоритм Дейкстры к определению кратчайшего расстояния в ориентированном графе?
- 5. Как работает алгоритм Дейкстры?
- 6. Как работает алгоритм динамического программирования применительно к задаче определения в графе кратчайших расстояний между вершинами?
Алгоритм Дейкстры – алгоритм на графах, который находит кратчайший путь между двумя данными вершинами в графе с неотрицательными длинами дуг. Также часто ставится задача расчёта кратчайшего пути от данной вершины до всех остальных. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации.
Описание
На вход алгоритма подаётся взвешенный ориентированный граф с дугами неотрицательного веса. На выходе получается набор кратчайших путей от данной вершины до других.
В начале расстояние для начальной вершины полагается равным нулю, а расстояния до всех остальных понимаются бесконечными. Массив флагов, обозначающих то, пройдена ли вершина, заполняется нулями. Затем на каждом шаге цикла ищется вершина с минимальным расстоянием до изначальной и флагом равным нулю. Для неё устанавливается флаг и проверяются все соседние вершины. Если рассчитанное ранее расстояние от исходной вершины до проверяемой больше, чем сумма расстояния до текущей вершины и длины ребра от неё до проверяемой вершины, то расстояние до проверяемой вершины приравниваем к расстоянию до текущей+ребро от текущей до проверяемой. Цикл завершается, когда флаги всех вершин становятся равны 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. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.
Шаг 2. Все вершины не выделены.
Шаг 3. Первая вершина объявляется текущей.
Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра , соединяющего текущую вершину с невыделенной.
Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход . Иначе, текущей становится найденная вершина . Она же выделяется.
Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.
Шаг 7. Переход на шаг 4.
В программной реализации алгоритма Дейкстры построим множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин. При этом будем использовать массив D , в который записываются длины кратчайших путей для каждой вершины. Когда множество S будет содержать все вершины графа , тогда массив D будет содержать длины кратчайших путей от начальной вершины к каждой вершине.
Помимо указанных массивов будем использовать матрицу длин C , где элемент C – длина ребра (i,j) , если ребра нет, то ее длина полагается равной бесконечности, то есть больше любой фактической длины ребер. Фактически матрица C представляет собой матрицу смежности , в которой все нулевые элементы заменены на бесконечность.
Для определения самого