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

Алгоритм определения кратчайших путей

Эта задача имеет большое значение в практических применениях. К ней сводятся многие задачи выбора наиболее экономичного (с точки зрения расстояния или стоимости) маршрута на имеющейся карте дорог, наиболее экономичного способа перевода динамической системы из одного состояния в другое и т.д. Существует много математических способов решения, но часто методы, основанные на теории графов, наименее трудоемки.

Рассмотрим задачу о кратчайшем пути. Пусть дан граф G(X), дугам которого приписаны веса (расстояния, стоимости и т.п.), задаваемые матрицей С = || c_ij ||.

Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s Î X до заданной конечной вершины t Î X при условии, что такой путь существует. В общем случае возможно С_ij > 0, С_ij < 0, С_ij = 0. Единственное ограничение состоит в том, чтобы в графе G(X) не было циклов с отрицательным суммарным весом.

Приведем очень простой и эффективный алгоритм Дейкстры решения этой задачи для случая С_ij ³ 0 " i, j. Алгоритм основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от s к этой вершине. Величины этих пометок постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это означает, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от s к рассматриваемой вершине. Пусть l(x_i) – пометка вершины x_i. Опишем основные этапы алгоритма.

Шаг 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₁ ко всем остальным вершинам. Постоянные пометки будем обозначать знаком ⁺.