§ 2. Алгоритмы построения кратчайших путей

Рассмотрим сеть (см. определение 1.6), состоящую из n узлов. Каждой дуге сети сопоставлена некоторая величина (вес), которая может интерпретироваться как расстояние между узлами, цена, время или энергия. Выделим в этой сети два узла: s – вход и t – выход. Рассмотрим кроме того, задачу нахождения кратчайшего пути из узла s в узел t. Будем предполагать, что в любой узел можно попасть из входа и из любого узла можно попасть на выход. Узлы, не удовлетворяющие этому свойству, можно удалить.

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

На рис. 3.4 представлена сеть, в которой имеется контур длиной . Для такой сети .

Рис. 3.4. Сеть, содержащая контур отрицательной длины.

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

Алгоритм Дейкстры применяется для сетей, не имеющих дуг с отрицательными весами, и состоит из двух этапов: на первом этапе находят длину кратчайшего пути, а на втором – строят сам путь.

Алгоритм Дейкстры называют также алгоритмом расстановки меток, так как основная идея алгоритма состоит в том, что каждой вершине приписывается метка, которая может быть временной и постоянной. Временная метка вершины равна длине некоторого пути до нее из исходной вершины, а постоянная метка равна длине кратчайшего пути. Алгоритм действует до тех пор, пока узел, являющийся концом пути, не получит постоянной метки.

Формализуем задачу. Рассмотрим сеть . Обозначим через соответственно начало и конец искомого пути . Предположим, что для любой дуги . Припишем метку каждому узлу .

Этап 1. (нахождение длины кратчайшего пути).

Будем обозначать текущий узел через u.

Шаг 0. (расстановка начальных меток). Присваиваем начальному узлу метку «0» и превращаем эту метку в постоянную: ( «*», приписанная метке означает, что она превращена в постоянную). Всем остальным узлам приписываем метки, равные +∞:

.

В качестве текущего узла выберем узел : .

Шаг 1. (изменение меток). Для всех узлов, непосредственно следующих из узла u, т.е. для всех (см. опр. 1.3), изменяем метки по следующему правилу:

. (3.1)

Шаг 2. (превращение метки в постоянную). Из всех узлов с временными метками выбираем в качестве постоянного узел с минимальным ее значением:

(3.2)

и выбираем этот узел в качестве текущего: u:=х.

Шаг 3. Проверяем условие . Если оно верно, то первый этап завершен: , в противном случае возвращаемся к шагу 1.

Этап 2. (нахождение кратчайшего пути методом последовательного возвращения).

Шаг 0. Выпишем все постоянные метки графа. В качестве текущего возьмем конечный узел пути: .

Шаг 1. Для всех узлов, непосредственно предшествующих узлу u, т. е. для всех (см. опр. 1.3), проверяем выполнение равенства:

(3.3)

Если оно верно, то дугу добавим в искомый путь и выберем узел х в качестве текущего: u:=х.

Шаг 2. Проверяем условие . Если оно верно, то второй этап завершен, в противном случае возвращаемся к шагу 1.

Замечание 3.2. Каждая метка в процессе выполнения алгоритма может либо уменьшаться, либо оставаться прежней.

Замечание 3.3. Если равенство (3.3) выполнено для нескольких узлов, то в качестве текущего рассмотрим любой из них.

Замечание 3.4. Алгоритм Дейкстры применим также и к неориентированным графам. При этом достаточно каждое ребро с весом рассматривать как пару дуг и того же веса.

Замечание 3.5. Алгоритм применяется только для сетей, для которых выполняется неравенство треугольника: .

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

Доказательство. Достаточно доказать, что постоянная метка каждого узла х равна длине кратчайшего пути . Используем метод индукции [3].

Пусть узел х получил постоянную метку на k-й итерации. Если , то справедливость утверждения очевидна, так как только s имеет постоянную метку, равную нулю. Предположим, что утверждение верно для узлов, получивших постоянные метки на итерациях . Обозначим -путь, построенный с помощью алгоритма в результате k итераций, Р* – кратчайший -путь. По условию .

Разобьем множество узлов Х на два подмножества: , где – множество узлов, имеющих постоянные метки, – множество узлов, имеющих временные метки перед началом k-й итерации. Тогда возможны две ситуации:

1. Пусть Р* содержит узлы из . Обозначим через первый узел пути, принадлежащий , а через – предшествующий узел пути. Тогда , и по предположению индукции – длина кратчайшего -пути, т. е.

.

Тогда

.

Поскольку метка временная,

по условию выбора постоянной метки.

Таким образом,

.

Следовательно, – кратчайший -путь.

2. Все узлы пути Р* входят в . Рассмотрим узлы и , такие, что и . Тогда

.

При этом узел х получает метку узла , используя условие минимальности. Таким образом, получаем

.

Следовательно, – кратчайший -путь. ■

Пример 3.1. Рассмотрим сеть , состоящую из пяти узлов и найдем кратчайший путь из узла в узел .

Рис. 3.5. Сеть

На рис. 3.6 представлена сеть , где узлы изображены кружками, внутри которых будем вписывать получаемые ими в результате работы алгоритма метки. На нулевом шаге алгоритма вход получает постоянную метку, равную нулю, остальные узлы – временные метки, равные бесконечности:

Рис. 3.6. Узел получил постоянную метку.

Множество узлов, непосредственно следующих за , , следовательно, они получат новые метки – 2 и 4, соответственно. При этом метка узла станет постоянной:

Рис. 3.7. Узел получил постоянную метку.

Множество , следовательно, меняем метку . При этом постоянную метку получает узел , так как это узел с наименьшей временной меткой.

Рис. 3.8. Узел получил постоянную метку.

На следующей итерации узел получает метку равную 9, постоянной становится метка узла .

Рис. 3.9. Узел получил постоянную метку.

На следующей итерации узел получает постоянную метку, равную 7.

Рис. 3.10. Длина кратчайшего пути до узла равна 7.

На рис. 3.11. показан кратчайший путь сети

Рис. 3.11. Кратчайший путь из в сети

Алгоритм Дейкстры можно модифицировать так, чтобы с его помощью можно было построить кратчайшие пути от узла до всех остальных узлов. В результате получим корневое ориентированное остовное дерево (см. определение 4.1), называемое деревом кратчайших путей из s графа G. Обозначим это дерево Т. Для построения Т необходимо изменить шаг 3 этапа 1 на шаг 3*.

Шаг 3*. Проверяем условие: все узлы имеют постоянные метки. Если верно, то первый этап закончен: , иначе возвращаемся к шагу 1.

Кроме того, необходимо заменить этап 2 на 2*.

Этап 2*. (нахождение дерева кратчайших путей).

Шаг 0*. Выпишем все постоянные метки графа.

Шаг 1*. Для всех выполнить: для всех , проверяем выполнение равенства

(3.4)

если верно, то дугу добавим в дерево Т: .

Заметим, что можно построить несколько деревьев кратчайших путей, выходящих из одного и того же узла. При этом сами деревья могут иметь разные веса. Задача построения дерева кратчайших путей минимального веса рассматривается в § 5.

Как уже отмечалось, алгоритм Дейкстры применим только в случае сети с неотрицательными весами. Рассмотрим пример сети, имеющей дугу с отрицательным весом, для которой с помощью алгоритма находим неверный кратчайший путь.

Пример 3.2. Найдем кратчайший путь из узла в узел . После первой итерации узлы и будут иметь постоянные метки, а узел – временную: .

После второй итерации узел приобретает постоянную метку

.

При этом очевидно, что длина кратчайшего пути из до равна единице.

Рис. 3.12. Некорректность работы алгоритма Дейкстры

для сети с произвольными весами.

Таким образом, для сетей с весами произвольного знака необходим другой алгоритм нахождения кратчайшего пути.