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

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

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

Найти кратчайший путь на графе от вершины 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).