Глава 8 КРАТЧАЙШИЕ ПУТИ

1. Введение

Пусть дан граф G = {X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей С = [сц]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s 6 X до заданной конечной вершины t Х, при условии, что такой путь сугцествует, т. е. при условии t в R (s). Здесь R (s) - множество, достижимое из вершины s, как это было определено в гл. 2. Элементы матрицы весов С могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с суммарным отрицательным весом. Если такой цикл Ф все же существует их, - некоторая его вершина, то, двигаясь от S к Xj, обходя затем Ф достаточно большое число раз и попадая наконец в t, мы получим путь со сколь угодно малым (- - - оо) весом. Таким образом, в этом случае кратчайшего пути не существует.

Если, с другой стороны, такие циклы существуют, но исключаются из рассмотрения, то нахождение кратчайшего пути (простой цепи) между s vi t эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами s и Л Это можно усмотреть из следующего факта. Если из каждого элемента Cij матрицы весов С вычесть достаточно большое число L, то получится новая матрица весов С - [с'ц], все элементы cij которой отрицательны. Тогда кратчайший путь от s к t - с исключением отрицательных циклов - необходимо будет гамильтоновым, т. е. проходящим через все другие вершины. Так как вес любого гамильтонова пути с матрицей весов С равен весу этого пути с матрицей С, но уменьшенному на постоянную величину (п - 1) -L, то кратчайший путь (простая цепь) от s к f с матрицей С будет кратчайшим гамильтоновым путем от s к t при первоначальной матрице С. Задача нахождения кратчайшего Гамильтонова пути намного сложнее, чем задача о кратчайшем пути; она обсуждается отдельно в гл. 10. Поэтому мы будем предполагать, что все циклы в G имеют неотрицательный суммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.

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

(i) Для заданной начальной вершины s найти кратчайшие пути между S и всеми другими вершинами Xi 6 X.

(ii) Найти кратчайшие пути между всеми парами вершин.

В последующих разделах будет показано, что почти все методы, позволяюпще решить задачу о кратчайшем (5-<)-пути, дают также (в процессе решения) и все кратчайшие пути от s к Х{ (Axi 6 X). Таким образом, они позволяют решить задачу с небольшими дополнительными вычислительными затратами. С другой стороны, задача (i) может быть решена либо га-кратным применением алгоритма задачи (ii), причем на каждом шаге в качестве начальной вершины s берутся различные вершины, либо однократным применением специального алгоритма.

В настоящей главе мы дадим общие алгоритмы решения сформулированных выше задач и частные алгоритмы для случаев, когда все Си неотрицательны. Эти частные случаи встречаются на практике довольно часто (например, когда с^ являются расстояниями), так что рассмотрение этих специальных алгоритмов оправдано. Мы будем предполагать, что матрица не удовлетворяет, вообще говоря, условию треугольника, т. е. не обязательно с,-; с^ --+ Ck) для всех i, i ш к. В противном случае кратчайший путь между Xi и Xj состоит из одной единственной дуги ) (х; Xj) и задача становится тривиальной. Если в графе G дуга (Xf, Xj) отсутствует, то ее вес полагается равным оо.

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

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

1) Если такая дуга существует Прим ред.

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

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

Задачи о кратчайшем пути, в которых на пути накладываются некоторые ограничения (см. [4], [12], [23]), в настоящей главе не рассматриваются, так как к ним непосредственно не применимы те методы расстановки пометок, на которых базируются все описанные здесь алгоритмы нахождения кратчайшего пути. Эти задачи с ограничениями часто настолько сложны, что соответствующие алгоритмы позволяют находить оптимальные решения лишь таких задач, размеры которых (например, число вершин) на несколько порядков меньше, чем у аналогичных задач без ограничений. Ряд важных задач с ограничениями, например задача о кратчайшем гамильтоновом пути, рассматривается в отдельных главах

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

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

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

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

2.1.1. Алгоритм Дейкстры {ctj 0) Пусть I (xi) - пометка вершины Xi.