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

Шаг 1. Присвоение начальных значений. Для исход­ной вершиныsположимl(s) = 0 и эта пометка будет по­сто­янной. Для всех других вершин имеем: 1(х_i) =x_is. Эти пометки временные. Положимp=sи составим мно­жество образов этой вершины:G(p).

Шаг 2. Обновление пометок. Для всехx_iG(p), помет­ки которых являются времен­ными, изменить пометки в соответствии с выражением:

1(х_i) = min [1(х_i), 1(р) + c(p, x_i)] (8)

Шаг 3. Превращение пометок в постоянные. Среди всех вершин с временными пометками найти та­куюx_i^*, для которойl(x_i^*) =min[l(x_i)]. Считать пометку вершиныx_i^*постоянной и положить р =x_i^*.

Шаг 4. Переход к шагу 2, если р  t. Останов при р = t. В случае, если требуется найти лишь путь от s к одной вершине t, следует окончание счета. Длина этого крат­чайшего пути будет 1(р).

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

Проиллюстрируем работу алгоритма на примере графа, изо­браженного на рис. 3.34. Матрица весов – в табл. 3.4. Граф является смешанным, т. е. ребра у него ориентирова-нные и неори­ентированные. Требуется найти все кратчайшие пути от x₁ко всем остальным вершинам. Постоянные пометки будем обозначать знаком⁺.

Шаг 1.l(x₁) = 0⁺, 1(x_i) =x_ix₁, р =x₁.

Первая итерация

Шаг 2.G(p) =G(x₁) = {х₂, х₇, х₈, х₉}. Все эти вершины имеют временные пометки.

Рис.3.34. Пример графа к алгоритму Дейкстры

Таблица 3.4. Матрица смежности с весами для графа
	х1	х2	х3	х4	x5	x6	x7	x8	x9
х1		10					3	6	12
х2	10		18				2		13
х3		18		25		20			7
х4			25		5	16	4
x5				5		10
x6			20		10		14	15	9
x7		2		4		14			24
x8	6				23	15			5
x9	12	13				9	24	5

В соответствии с формулой (8) уточняем пометки:

l(х₂) = min(, 0⁺ + 10) = 10; l(х₇) = 3; l(х₈) = 6; l(x₉) = 12.

Шаг 3.min(10, 3, 6, 12,) = 3

х₂ х₇ х₈ х₉ х₃, х₄, х₅, х₆

Вершина х₇ получает постоянную пометку: 1(х₇) = З⁺ .

Далее р = x₇.

Шаг 4. Так как не все вершины имеют постоянные пометки, то переходим к шагу 2. На рис. 3.35 приведены значения пометок вершин графа. Здесь выделены вершины с постоянными пометками.

Рис. 3.35. Пометки в начале второй итерации