39. Метод Дейкстры

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

Найти кратчайший путь на графе от вершины L до вершины D (рис.2).

Рис.2. Взвешенный неориентированный граф

Запишем алгоритм в виде последовательности шагов.

Шаг 1. Определяются расстояния от начальной вершины L до всех остальных .

Длина пути до выбранной вершины	Выбранная вершина	Невыбранные вершины
		B		G	N	R	D	S	M	A
0	L	7		∞	10	∞	∞	∞	∞	∞
7	B

Шаг 2. Выбираем наименьшее расстояние от L до B, найденная вершина В прини-

мается за вновь выбранную. Найденное наименьшее расстояние добавляется к длинам ребер

от новой вершины В до всех остальных. Выбирается минимальное расстояние от В до N. Новая вершина N принимается за выбранную.

Длина пути до выбранной вершины	Выбранная вершина	Невыбранные вершины
		B		G	N	R	D	S	M	A
0	L	7		∞	10	∞	∞	∞	∞	∞
7	B	∞		16	10	∞	∞	∞	∞	34
10	N

Для наглядности в дальнейшем вместо знака ∞ будем ставить знак “-“.

Шаг 3. Определяются расстояния от вершины N до всех оставшихся (за исключением

L и B) .

Длина пути до выбранной вершины	Выбранная вершина	Невыбранные вершины
		B		G	N	R	D	S	M	A
0	L	7		∞	10	∞	∞	∞	∞	∞
7	B	∞		16	10	∞	∞	∞	∞	34
10	N	∞		16	∞	41	∞	∞	∞	34
16	G

Расстояние от вершины L через вершину N до вершины G равно 18. Это расстояние

больше, чем расстояние LB+BG= 16, поэтому оно не учитывается в дальнейшем.

Продолжая аналогичные построения, построим таблицу. Таким образом, найдена

длина кратчайшего пути между вершинами L и D (44 условных единицы).

Траектория пути определяется следующим образом.

Осуществляем обратный просмотр от конечной вершины к начальной.

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

Длина пути до выбранной вершины	Выбранная вершина	Невыбранные вершины
		B	G	N	R	D	S	M	A
0	L	7	-	10	-	-	-	-	-
7	B	-	16	10	-	-	-	-	34
10	N	-	16	-	41	-	-	-	34
16	G	-	-	-	41	-	16+11= =27	-	34
27	S	-	-	-	41	27+17= =44	-	27+15= =42	34
34	A	-	-	-	41	44	-	42 [34+15]	-
41	R	-	-	-	-	44 [41+32]	-	42	-
42	M	-	-	-	-	44 [42+21]	-	-	-

Min

В этом столбце минимальная длина, равная 27, указывает следующую вершину G,

к которой следует перейти, и т.д. Таким образом, получаем траекторию пути:

( L, B, G, S, D ).