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

1. Введение

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

Если, с другой стороны, такие циклы существуют, но исключаются из рассмотрения, то нахождение кратчайшего пути (простой цепи) между эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами Это можно усмотреть из следующего факта. Если из каждого элемента матрицы весов С вычесть достаточно большое число то получится новая матрица весов все элементы которой отрицательны. Тогда кратчайший путь от с исключением отрицательных циклов — необходимо будет гамильтоновым, т. е. проходящим через все другие вершины. Так как вес любого гамильтонова пути с матрицей весов С равен весу этого пути с матрицей С, но уменьшенному на постоянную величину то кратчайший путь (простая цепь) от с матрицей С будет кратчайшим гамильтоновым путем от при первоначальной матрице С. Задача нахождения кратчайшего Гамильтонова пути намного сложнее, чем задача о кратчайшем пути; она обсуждается отдельно в гл. 10. Поэтому мы будем предполагать, что все циклы в имеют неотрицательный суммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа не могут иметь отрицательные веса.

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

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

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

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

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

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

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

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

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

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