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

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

Пусть G(V, R) — некоторый граф. Будем считать, что каждому ребру г G R графа поставлено в соответствие некоторое неотрица­тельное число d(r) J? О, называемое длиной или весом ребра. При этом граф G(V, R) называется взвешенным. Пусть последователь­ность ri,r2, ■ ■ ■ ,rk ребер графа образует путь. Длиной пути назы­вается сумма

d(r 1) + d(r₂) + • • • + d(r_k)

длин всех ребер, образующих данный путь.

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

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

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

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

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

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

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

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

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

# А = 1, #Е = 2, #Н = 3, # Р = 4, #8 = 5, #Т = 6. Выполним подробно несколько первых шагов алгоритма.

—               Полагаем г>[₀] = Э, р = 1, к = 0.

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

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

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

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

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

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

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

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

 

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

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

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

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

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

—               максимальный путь 1 — 2 — 5 имеет длину 2;

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

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

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