2. Кратчайший путь между двумя заданными вершинами s и t

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

2.1. Случав неотрицательной матрицы весов

Наиболее эффективный алгоритм решения задачи о кратчайшем -пути первоначально дал Дейкстра [10]. В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от к этой вершине. Эти пометки (их величины) постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от к рассматриваемой вершине. Опишем этот метод подробно.

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

Пусть пометка вершины

Присвоение начальных значений

Шаг 1. Положить и считать эту пометку постоянной. Положить для всех считать эти пометки временными. Положить

Обновление пометок

Шаг 2. Для всех пометки которых временные, изменить пометки в соответствии со следующим выражением:

Превращение пометки в постоянную

Шаг 3. Среди всех вершин с временными пометками найти такую, для которой ].

Шаг 4. Считать пометку вершины х постоянной и положить

Шаг (Если надо найти лишь путь от Если то является длиной кратчайшего пути.

Останов.

Если перейти к шагу 2.

(ii) (Если требуется найти пути от ко всем остальным вершинам.)

Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. Останов.

Если некоторые пометки являются временными, перейти к шагу 2.

Доказательство того, что вышеприведенный алгоритм действительно дает кратчайшие пути, чрезвычайно простое, дадим набросок этого доказательства.

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

Пусть кратчайший путь от не проходит целиком по и содержит по крайней мере одну вершину из и пусть первая такая вершина в этом пути. Так как по предположению с неотрицательны, то часть пути от должна иметь неотрицательный вес Это, однако, противоречит утверждению, что наименьшая временная пометка, и, следоватёльно, кратчайший путь к х проходит полностью по вершинам множества и поэтому является его длиной.

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

Если требуется найти кратчайшие пути между и всеми другими вершинами полного связного графа с вершинами, то в процессе работы алгоритма выполняются операций сложения и сравнения на шаге 2 и еще операций сравнения на шаге 3. Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины являются временными, а для этого нужно еще операций сравнения. Эти величины являются верхними границами для числа операций, необходимых при отыскании кратчайшего пути между заданными вершинами Они действительно достигаются, если окажется, что вершина будет последней вершиной, получившей постоянную пометку. (В [22] Джонсон предложил так называемый метод сортировки, позволяющий уменьшить число операций на шаге 3.)

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

Если кратчайший путь от до любой вершины является единственным, то дуги этого кратчайшего пути образуют ориентированное дерево (см. предыдущую главу) с корнем Если существует несколько «кратчайших» путей от к какой-либо другой вершине, то при некоторой фиксированной вершине соотношение (8.2) будет выполняться для более чем одной вершины В этом случае выбор может быть либо произвольным (если нужен какой-то один кратчайший путь между либо таким, что рассматриваются все дуги входящие в какой-либо из кратчайших путей, и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф, называемый базой относительно или кратко — -базой.

2.1.2. Пример.

Рассмотрим граф, изображенный на рис. 8.1, где каждое неориентированное ребро рассматривается как пара противоположно ориентированных дуг равного веса. Матрица

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

Рис. 8.1. Граф из примера 2.1.2.

Постоянные пометки будем снабжать внаком остальные пометки рассматриваются как временные.

Алгоритм работает так:

Шаг 1.

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

Шаг 2. — все пометки временные. Возьмем сначала Из (8.1) получаем

аналогично

Шаг 3. соответствует

Шаг 4. х· получает постоянную пометку

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Пометки в начале следующей итерации показаны на рис.

Вторая итерация

Шаг 2. - все пометки временные. Из соотношения (8.1) имеем

аналогично Пометки изображены на рис. 8.2 (б).

Шаг 3. соответствует

Шаг 4. получает постоянную пометку

Шаг 5. Перейти к шагу 2.

Третья итерация

Шаг 2. - только вершины имеют временные пометки; из соотношения (8.1) получаем

и аналогично

Шаг 3. соответствует

Шаг 4. получает постоянную пометку

Шаг 5. Перейти к шагу 2.

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

(кликните для просмотра скана)

непосредственно предшествующую в кратчайшем пути от вершина должна удовлетворять соотношению

Единственной такой вершиной является Далее, применяем второй раз соотношение (8.2), беря получаем вершину непосредственно предшествующую в кратчайшем пути от Вершина удовлетворяет соотношению

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