Поиск кратчайших путей между отдельными вершинами графа

Первый эффективный алгоритм решения задачи нахождения кратчайшего пути в графе между двумя вершинами, при условии, что все дуги графа имеют положительную длину, предложил в 1959 г. Е.Дейкстра.

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

Начальная установка. Все вершины и дуги графа не окрашены. Каждой вершине в ходе выполнения алгоритма приписывается число (пометка) d (x), равное длине пути из начальной вершины S в вершину x. Причем, если вершина x окрашена, то d (x) - длина кратчайшего пути из S в x (постоянная пометка).

Положить d (x)=¥ для всех вершин x.

Шаг 1. Положить d (S)=0, y = S и окрасить вершину S. Здесь y - последняя из окрашенных вершин.

Шаг 2. Для каждой неокрашенной вершины x следующим образом пересчитать величину d (x):

d (x)=min{ d (x), d (y)+ a (y, x)}, (6.1)

где a (y, x) -длина дуги (y, x). Если d (x)= ¥ для всех неокрашенных вершин x, закончить процедуру: в исходном графе отсутствует путь из вершины S в неокрашенные вершины. В противном случае окрасить ту из вершин x, для которой величина d (x) является наименьшей. Кроме того, окрасить дугу, ведущую в выбранную на данном шаге вершину x (для этой дуги достигается минимум в соответствии с выражением 6.1). Положить y = x.

Шаг 3. Если y = t, закончить процедуру: кратчайший путь из S в t, состоящий из окрашенных дуг, найден. Его длина равна d (t). В противном случае перейти к шагу 2.

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

Рассмотрим работу алгоритма 3 при поиске кратчайшего пути из вершины S в вершину t в графе, изображенном на рисунке 6.1. Результаты работы алгоритма сведены в табл. 6.1. Дерево кратчайших путей представлено на рис. 6.2.

Таблица 6.1. Этапы поиска кратчайшего пути из вершины S в вершину t в графе, изображенном на рис. 6.1, согласно алгоритму 3

Номер итерации (шаг)	Изменение величин d (x) для неокрашенных вершин	Окрашивание
		дуг	вершин
Нач.уст.	d (v i)=µ, i=1,…,6	-	-
1 (Шаг 1)	d (S)= d (v 2)=0	-	y = v 2
2 (Шаг 2)	d (v 1)=min{ d (v 1), d (y)+ a (y, v 1)}= min{µ,0+1}=1 d (v 3)=min{ d (v 3), d (y)+ a (y, v 3)}= min{µ,0+9}=9	(v 2, v 1)	y = v 1 y ¹ t
3 (Шаг 2)	d (v 3)=min{9,1+7}=8 d (v 4)=min{µ,1+2}=3	(v 1, v 4)	y = v 4 y ¹ t
4 (Шаг 2)	d (v 3)=min{8,3+4}=7 d (v 5)=min{µ,3+8}=11 d (v 6)=min{µ,3+5}=8	(v 4, v 3)	y = v 3 y ¹ t
	5 (Шаг 2)	d (v 5)=min{11,7+5}=11 d (v 6)=8 (Посчитано на 4 итерации)	(v 4, v 6)	y = v 6 y = t КОНЕЦ

Корректность алгоритма поясняется следующими рассуждениями. Обратим внимание на тот факт, что существенным образом используется положительность весов дуг. Пусть на некотором этапе А и В - множества вершин с постоянными и временными пометками. В конце шага 2 всякая временная пометка - это длина кратчайшего пути между вершиной S и помеченной вершиной, проходящего только через вершины множества А. Но при этом оказывается, что для вершины x, окрашиваемой на шаге 2 - это вообще длина кратчайшего пути из S в x. Действительно, если бы это было не так, то в В существовала бы вершина x ¢, через которую проходит кратчайший путь из S в x. При этом за x ¢ можно взять такую вершину на этом пути, что все предшествующие x ¢ вершины пути лежат в множестве А. Пусть a и b - длины частей этого пути от S к x ¢ и от x ¢ к x. Так как веса всех дуг положительны, то a, b >0. Так как этот путь кратчайший, то a+b< d (x), но отсюда следует, что a= d (x ¢)< d (x). А это соотношение противоречит минимальности пометки x среди всех временных пометок вершин.

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

Выделим теперь свойство задачи, которое допускает её правильное решение описанным алгоритмом. Любая часть решения также является решением, то есть если S, x ₁,..., x_n, t - кратчайший путь из S в t, то для любого i =1,2,..., n путь S, x ₁,..., x_i является кратчайшим из S в x_i. Подобное свойство является одним из важнейших свойств метода, известного под названием динамического программирования.

«Динамическое программирование, в сущности, вычисляет решение для всех подзадач. Вычисление идет от малых подзадач к большим, ответы запоминаются в таблице. Преимущество этого метода состоит в том, что раз уж эта задача решена, её ответ где-то хранится и никогда не вычисляется заново» [8]. В алгоритме Дейкстры на каждом шаге решается некоторая подзадача, а именно: находится кратчайший путь из начальной вершины S в некоторую вершину x. Результат её решения – длина кратчайшего пути из S в x (постоянная пометка вершины x) запоминается в массиве и далее не пересчитывается.

Упражнения:

1. Алгоритм 3 находит кратчайший путь из начальной вершины S в конечную вершину t. Измените алгоритм, чтобы находились кратчайшие пути из вершины S до всех оставшихся вершин графа.

2. Реализуйте и исследуйте на эффектвность алгоритм Дейкстры.

Указание. Для хранения окрашенных дуг используйте приём, описанный в разд. 5.2, упр.1.

3. Узким местом пути называется кратчайшая из входящих в него дуг. Задача об узких местах пути - задача поиска такого пути между двумя вершинами, в котором длина кратчайшей дуги максимальна.

Измените алгоритм Дейкстры для решения задачи об узких местах пути.

Придумайте реальные задачи, сводящиеся к задаче об узких местах пути.

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

Модифицируйте алгоритм Дейкстры для решения задачи о путях с усилением.

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

Исходное предположение в алгоритме Дейкстры состояло в неотрицательности длин дуг исходного графа. Действительно, применение рассмотренного алгоритма к графу, изображенному на рис. 6.2, дает ошибочный результат: в качестве кратчайшего пути будет указан путь, состоящий из дуги (S, t), не являющийся таковым.

Задачу поиска кратчайшего пути в графе с отрицательными весами дуг решает алгоритм Форда, представляющий собой модификацию алгоритма Дейкстры. Модификация алгоритма Дейкстры состоит в следующем:

1. На шаге 2 пересчет величин d (x) с помощью выражения 6.1 производится для всех вершин, а не только для неокрашенных вершин. Следовательно, числа d (x) могут уменьшаться как для неокрашенных, так и для окрашенных вершин.

2. Если для некоторой окрашенной вершины x происходит уменьшение величины d (x), то с этой вершины и инцидентной ей окрашенной дуги окраска снимается.

3. Процедура заканчивается только тогда, когда все вершины окрашены и когда после выполнения шага 2 ни одно из чисел d (x) не меняется.

Алгоритм Форда не решает задачи поиска кратчайшего пути при наличии в исходном графе контура, имеющего отрицательную длину. Пример такого графа представлен на рис. 6.3.

Контур отрицательной длины образуют дуги (a, b),(b, a). Длина контура равна 3-4=-1, повторяя этот контур, можно получить путь со сколь угодно малой по величине длиной.

Для обнаружения контура отрицательной длины можно обычным образом применять алгоритм Форда, но в процессе его работы необходимо учитывать, сколько раз окрашиваются отдельные вершины. Как только число окрашиваний какой-либо вершины достигает n, где n - число вершин графа, процедуру можно остановить: исходный граф содержит контур отрицательной длины.