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

Шаг 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₁.