3.3. задача о кратчайшем пути

3.3. задача о кратчайшем пути

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

Пусть G(V, R) — некоторый граф. Будем считать, что каждому ребру г Є R графа поставлено в соответствие некоторое неотрицательное число d(r) ^ 0, называемое длиной или весом ребра. При этом граф G(V,R) называется взвешенным. Пусть последовательность гі,Г2, ■ ■ ■ ,rk ребер графа образует путь. Длиной пути называется сумма

d(ri) + d(r2) + ■-. + d(rfc) длин всех ребер, образующих данный путь.

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

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

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

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

на основе алгоритма перечисления путей;

методом ДП на графе.

В настоящем разделе рассмотрим первый из них.

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

Применим рассмотренный метод к решению задачи о кратчайшем пути для графа, представленного на рис. 3.4. (Имеющиеся на рисунке расчеты и стрелки имеют отношение к решению задачи методом ДП, и в настоящий момент их принимать во внимание не следует.) Началь

ной является вершина S, конечной — вершина Е. В данном примере вершины графа удобно упорядочить по латинскому алфавиту; при этом они будут иметь следующие порядковые номера:

#А = 1, #Е = 2, #Н = 3, #Р = 4, #S = 5, #Т = 6.

Выполним подробно несколько первых шагов алгоритма.

Полагаем ущ = S, р = 1, к = 0.

Поскольку вершина S не совпадает с конечной вершиной Е, то переходим к п. 3.

Для вершины S смежными являются вершины А,Н,Р,Т, причем ни одна из них к текущему пути не относится. Поскольку р = 1, то минимальный допустимый номер 1 имеет вершина А, которая и является искомым продолжением. Текущий путь принимает вид S —А, индекс р полагается равным 1, параметр fc —равным 1. Переход к п. 2.

Поскольку вершина А не совпадает с конечной вершиной Е, то переходим к п. 3.

Для вершины А смежными являются все вершины графа, но в текущий путь не входят только вершины Е, Н, Р, Т. Поскольку р = 1, то минимальный допустимый номер из них имеет вершина Е, которая и является искомым продолжением. Текущий путь принимает вид S —А —Е, индекс р полагается равным 1, параметр к — равным 2. Переход к п. 2.

Вершина Е является конечной вершиной; это означает, что очередной из путей, соединяющих заданные начальную и конечную вершины, найден. Вычисляем длину пути (она составляет 10 + 7 = 17), запоминаем сам путь и его длину. (Отметим, что для найденного пути ущ = S, У[ц = А, ущ = Е.) Переход к п. 4.

Укорачивание пути является возможным. Вершина Е текущего пути отбрасывается. Текущий путь принимает вид S — А, индекс р полагается равным ф Е + 1 = 3, параметр к — равным 1. Переход к п. 3.

Для вершины А в настоящий момент в отличие от рассмотренной выше ситуации индекс р = 3. Поскольку # Е = 2, # Н = 3, то выбирать продолжением вершину Е нельзя (это уже было сделано ранее), и допустимым продолжением является вершина Н. Текущий путь принимает вид S —А —Н, индекс р полагается равным 1, параметр & —равным 2. Переход к п. 2 и т. д. по алгоритму.

Результаты проводимых расчетов частично (по причине их громоздкости и элементарности многократно повторяемых ситуаций) представлены в следующей таблице:

связанных с графами задач. Некоторые из его приложений будут рассмотрены далее.

Замечание 1. Рассмотренный метод позволяет решить задачу о кратчайшем пути и при наличии отрицательных длин ребер.

Замечание 2. На основе алгоритма перечисления путей можно решить и задачу о максимальном пути: найти путь максимальной длины, соединяющий две заданные вершины графа. Подчеркнем, что в задаче о максимальном пути существенно, рассматривается максимальный путь или цепь. Например, для изображенного на рис. 3.5 графа с равными единице длинами всех ребер, начальной вершиной 1 и конечной вершиной 5, справедливо следующее:

максимальная цепь 1 — 2 — 3 — 4 — 2 — 5 имеет длину 5;

маршрут из 1 в 5 может быть выбран сколь угодно длинным за счет многократного обхода цикла 2 — 3 — 4 — 2.

Если последняя вершина текущего пути совпадает с конечной вершиной, то очередной из искомых путей найден; его длина вычисляется и заносится во второй столбец таблицы. Прочерк «—» в этом столбце означает, что построенный путь не доходит до конечной вершины. В отдельных ситуациях, например, на пути S —А — Р —Т —Н, мы попадаем в «тупик», не дойдя до конечной вершины; в данном случае все вершины, смежные с конечной вершиной пути Н, уже входят в текущий путь, и провести удлинение без повторения вершин невозможно.

Проведенное до конца построение всех путей показывает, что кратчайшим путем от вершины S к вершине Е является путь S —Н — А — Р — Е, а его длина равна 12.

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

Задание. Решить задачу о максимальном пути для изображенного на рис. 3.4 графа с начальной вершиной А и конечной вершиной Н методом перечисления путей.