3.7. Задача о кратчайшем пути на ориентированных графах

Постановка и методы решения задачи о кратчайшем пути на оргра фах полностью аналогичны ситуации для неориентированных графов Пусть G(V, R) — ориентированный граф. Будем считать, что каждое дуге г орграфа поставлено в соответствие некоторое неотрицательно число d(f) > 0, называемое длиной или весом дуги. Пусть последова тельность дуг fi,f₂₎... образует путь. Длиной пути fi, г₂,..., rj называется сумма

d(fi) + d(f₂) + ...+d(f_fc)

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

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

Решение задачи о кратчайшем пути на орграфах может быть про ведено следующими методами, аналогичными рассмотренным выш< методам решения задачи для неориентированных графов:

1)               методом перечисления путей;

2)               методом ДП на графе;

3)               с помощью алгоритма Дийкстры, упоминавшегося выше по тек сту и представляющего, по существу, один из вариантов ме тода ДП.

Рассмотрим указанные методы решения на примере орграфа, изоб раженного на рис. 3.16, в котором начальной является вершина 5, ко нечной — вершина 3. (На данном рисунке уже приведены результата, расчетов по методу ДП.)

1. Рассмотрим метод перечисления путей. В рассматриваемом^ при мере вершины орграфа естественно упорядочить по их номерам. Kai и для неориентированных графов, на каждом шаге алгоритма решенш задачи имеется некоторый построенный текущий путь

вершин на данном шаге алгоритма. Отличие от случая неориентирован­ных графов заключается лишь в операции удлинения: для удлинения текущего пути просматриваются не просто все вершины графа, смеж­ные с конечной вершиной Уущ текущего пути, а только следующие за ней вершины с учетом ориентации дуг. Проведение решения задачи данным методом не представляет сложностей. Результаты расчетов могут быть представлены в виде следующей таблицы:

 

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

5—>7—>6—>4—>1—>3,

а его длина равна 15.

2. Рассмотрим метод ДП решения поставленной задачи. Отличие его от метода решения задачи для неориентированных графов заклю­чается лишь в том, что при расчете оценок рассматриваются неза­нятые вершины, не просто смежные с занятыми, а предшествующие им с учетом ориентации дуг. Проведем решение задачи о кратчайшем пути для заданного на рис. 3.16 орграфа методом ДП, ведя запись на самом графе. Напомним, что через Ь(у) обозначается длина крат­чайшего пути из вершины V в конечную вершину, а через Е(у) — оценка длины кратчайшего пути (см. разд. 3.4).

—               Полагаем Ь(3) = 0, ставим 0 около вершины 3 и объявляем данную вершину занятой, а все остальные — свободными.

—               Поскольку начальная вершина 5 не является занятой, то при­ступаем к расчету оценок незанятых вершин. Для занятой вер­шины 3 предшествующими являются вершины 1 и 5, причем обе они свободны. Вычисляем оценки для этих вершин:

Е( 1) = д(\ 3) + Ь(3) = 5 + 0 = 5, Е(5) = <*(5 3) + ЦЗ) = 20 + 0 = 20.

Полученные значения записываем на графе около вершин 1 и 5, которые переходят в группу пробных вершин. Отмечаем (например, короткими стрелками) дуги 1 —► 3 и 5 —► 3. Из двух пробных вершин 1 и 5 значение оценки для вершины 1 минимально и равно 5. Полагаем

Ь(1) = Е(1) = 5,

отмечаем жирным шрифтом данное значение на графе я объ­являем вершину 1 занятой.

—               Начальная вершина 5 не является занятой, поэтому продол­жаем расчет оценок. Занятыми в настоящий момент являются вершины 1 и 3, а предшествующими им незанятыми служат вершины 4 и 5. При этом вершина 5 имеет оценку, исходящая дуга 5 —> 3 уже учтена выше и не требует повторного рас­смотрения. Вершина 4 является свободной, а дуга 4 —> 1 еще

не рассматривалась. Вычисляем оценку для этой вершины:

Е(4) = <*(4 -> 1) + Ц\) = 4 + 5 = 9.

Полученное значение записываем на графе около вершины 4. Из двух пробных вершин 4 и 5 минимальное значение 9 оценка принимает для вершины 4. Полагаем

Ц4) = Е( 4) = 9,

отмечаем жирным шрифтом данное значение на графе и объ­являем вершину 4 занятой. Отмечать стрелкой дугу 4 —> 1 нет необходимости, поскольку из вершины 4 исходит только одна эта дуга, и неоднозначности возникнуть не может.

—               Начальная вершина 5 еще не стала занятой, поэтому продол­жаем расчет оценок. Занятыми в настоящий момент являются вершины 1,3,4, предшествующими им незанятыми служат вер­шины 5,6, 7, причем вершины 6 и 7 свободны. Вычисляем оценки для этих вершин:

Е(6) = (1(6 -> 4) + Щ) = 1 + 9 = 10, Е(7) = (1(7 -> 4) + Щ) = 4 + 9 = 13,

записываем полученные значения на графе и переводим их в число пробных вершин. Отмечаем стрелкой дугу 7 —> 4 (от­мечать дугу 6 —> 4 нет необходимости, поскольку из вершины 6 исходит только одна эта дуга). Для вершины 5 уже известна оценка Е(5) = 20, рассчитанная ранее; сейчас эту оценку необ­ходимо откорректировать, поскольку с момента ее вычисления появилась новая занятая вершина 4, следующая за 5. Вычисляем

т = (1(5 4) + Щ) = 8 + 9 = 17.

Поскольку т < Е(5), то полагаем Е(5) = 17, и ранее установлен­ную на дуге 5 —> 3 стрелку переносим на дугу 5 —> 4. Полученные значения оценок записываем на графе около соответствующих вершин. Из пробных вершин 5, 6, 7 минимальное значение 10 оценка принимает для вершины 6. Полагаем

Ц6) = Е( 6) = 10,

отмечаем жирным шрифтом данное значение на графе и объ­являем вершину 6 занятой.

—               Начальная вершина 5 по прежнему не стала занятой. Занятыми являются вершины 1, 3, 4, 6, предшествующими им незаня­тыми—вершины 5 и 7. Исходящие из 5 дуги уже учтены ранее.

Вершина 7 имеет оценку Е(7) = 13, причем дуга 7 —>• 6 еще не рассматривалась. Корректируем оценку, вычисляя

m = d(7 6) + L(6) = 12.

В ходе корректировки оценка уменьшается, поэтому полагаем Е(7) = 12, ранее установленная на дуге 7 —>• 4 стрелка перено­сится на дугу 7 —> 6. Полученные значения оценки записываем на графе. Из пробных вершин 5 и 7 минимальное значение 12 оценка принимает для вершины 7. Полагаем

Ц 7) = Е{ 7) = 12,

отмечаем жирным шрифтом данное значение на графе и объ­являем вершину 7 занятой.

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

m = d(5 -> 7) + L(7) = 15.

Поскольку m < Е(5) = 17, то полагаем Е(Ь) = 15, и ранее установленную на дуге 5 —> 4 стрелку переносим на дугу 5 —> 7. Полученное значение оценки записываем на графе. В настоящий момент имеет оценку только вершина 5, а вершина 2 является свободной. Полагаем

Ц 5) = Е(Ъ) = 15,

отмечаем жирным шрифтом данное значение на графе и объ­являем вершину 5 занятой.

—               Начальная вершина 5 стала занятой, причем L(5) = 15; следова­тельно, длина кратчайшего пути из 5 в 3 равна 15. Отметим, что в ходе расчетов вершина 2 осталась свободной, поскольку она не имеет последующих вершин и не мо^ет «получить оценки»; очевидно, что в силу отсутствия исходящих из 2 дуг не суще­ствует ни одного пути из 5 в 3, проходящего через вершину 2. Все проведенные выше расчеты составили этап, аналогичный этапу условной оптимизации классического метода ДП.

Построение кратчайшего пути представляет собой аналог этапа безусловной оптимизации. Кратчайший путь строится начиная с вер­шины 5 с использованием установленных на дугах стрелок, оконча­тельное распределение которых представлено на рис. 3.16. На дугах 6 —> 4 и 4 —> 1 стрелок не установлено, но у вершин 6 и 4 имеется только по одной исходящей дуге, и направление движения в данном случае определяется однозначно. Таким образом, кратчайший путь составляется из дуг 5 —► 7, 7 —> 6, 6 —► 4, 4 —► 1, 1 —> 3, т. е. имеет вид

5—>7—>6—>4—>1—>3.

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

3. Алгоритм Дийкстры, как уже отмечалось выше для случая неориентированных графов, представляет собой один из вариантов метода ДП, предписывающий начинать расчет длин кратчайших пу- тейс начальной вершины, а построение самого кратчайшего пути на­чинать с конечной вершины. Таким образом, порядок расчетов в ал­горитме Дийкстры «симметричен» по отношению к рассмотренному нами методу ДП. Детальное рассмотрение алгоритма Дийкстры пред­лагается читателям провести самостоятельно.

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

 

В первом столбце V таблицы записываются все вершины орграфа; порядок записи может быть произвольный, но лучше упорядочивать вершины в соответствии с их обозначениями по номерам или по алфа­виту. Для каждой вершины организуется свой строчный фрагмент. Во втором столбце го для каждой из вершин записываются все последую­щие вершины. Если таких нет, то это отмечается прочерком «— ». По существу, первые два столбца полностью задают структуру орграфа. В третьем столбце с1(у —> го) записываются длины дуг от вершин, ука­занных в первом столбце, к последующим вершинам, указанным во втором столбце. Таким образом, первые три столбца содержат все ис­ходные данные задачи. Заполнение первых трех столбцов представляет собой аналог предварительного этапа классического метода ДП.

Последующие два столбца отделяются от первых трех двойной вер­тикальной линией и уже непосредственно связаны с решением задачи. В четвертый столбец заносятся оценки Е(у) = с1(у —> го) + Ь(го), вычис­ляемые при условии, что значение функции Ь (го) уже известно для вер­шины го. В последний пятый столбец заносятся значения функции Ь(ь), равные минимальному значению из соответствующих оценок. Строки, на которых достигается минимальное значение, отмечаются знаком «/» (это отметки играют роль стрелок, устанавливаемых в ходе решения на дугах орграфа, и являются аналогами условно-оптимальных зна­чений управления из классического принципа оптимальности). Запол­нение в ходе расчетов последних двух столбцов представляет собой аналог этапа условной оптимизации классического метода ДП.

Для рассматриваемого в качестве примера орграфа соответствую­щая таблица имеет следующий вид:

 

Первые три столбца заполняются в соответствии с заданной струк­турой орграфа. Заполнение правой части таблицы начинается с за­писи 0 в пятый столбец для конечной вершины 3. Далее расчет и за­полнение таблицы проводятся по описанным выше правилам, причем вычисления могут идти не по порядку строк, а вразброс. Для контроля логики решения и последовательности расчетов в приведенной таблице в квадратных скобках «[ ]» указаны порядковые номера вычисления оценок и значений функции Ь(у).

После завершения заполнения таблицы строится решение задачи с использованием установленных отметок. Длина кратчайшего пути является значением функции Ь для начальной вершины 5 и равна 15. Кратчайший путь строится следующим образом. Рассматриваем строч­ный фрагмент, отвечающий начальной вершине 5. В этом фрагменте знак «/>> указывает на вершину 7. Следовательно, искомый путь со­держит дугу 5 —► 7. Далее, рассматриваем строчный фрагмент, отвеча­ющий вершине 7. В этом фрагменте знак «/» указывает на вершину 6.Следовательно, искомый путь содержит дугу 7 —> 6. Продолжая ана­логично, получим весь кратчайший путь

5—>7—>6—>4—>1—>3.

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

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