5. Нахождейие К кратчайших путей между двумя заданными вершинами

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

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

Мы будем здесь предполагать, что рассматриваются только простые цепи. И хотя кратчайший путь необходимо должен быть простой цепью (при условии, что граф не содержит циклов отрицательного веса), но второй, третий и т. д. кратчайшие пути не обязаны быть такими даже в случае, когда все положительны. Задача нахождения К кратчайших путей без требования, что они являются простыми цепями, намного проще, и для ее решения Хоффман и Пэвли [20], Сакарович [32], Веллман и Калаба предложили итерационные методы, аналогичные описанным выше. Однако модифицирование этих методов с целью получения простых цепей осуществить не совсем легко, а так как почти во всех, практических приложениях алгоритма нахождения К кратчайших путей требуются именно простые цепи, то мы опишем метод, предложенный Иеном [35] и позволяющий находить К кратчайших простых цепей.

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

Первый подпуть (совпадающий с ) пути называется его корнем и

обозначается второй подпуть пути называется ответвлением и обозначается через

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

5.1. Описание алгоритма

Присвоение начальных значений

Шаг 1. Найти Положить Если существует только один кратчайший путь включить его в список и перейти к шагу 2. Если таких путей несколько, но меньше, чем К, включить один из них в список а остальные в список Перейти к шагу 2. Если существует К или более кратчайших путей та задача решена. Останов.

Нахождение всех отклонений

Шаг 2. Найти все отклонения кратчайшего пути для всех выполняя для каждого шаги с 3-го по 6-й.

Шаг 3. Проверить, совпадает ли подпуть, образованный пер. выми вершинами пути с подпутем, образованным первыми вершинами любого из путей . Если положить с в противном случае ничего не изменять. (При выполнении алгоритма вершина Ху обозначается Перейти к шагу 4.

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

Шаг 5. Построить соединеняя и поместить в список

Шаг 6. Заменить элементы матрицы весов, измененные на шаге их первоначальными значениями и возвратиться к шагу 3.

Выбор кратчайших отклонений

Шаг 7. Найти кратчайший путь в списке Обозначить этот путь и переместить его из Если то алгоритм

заканчивает работу и дает требуемый список К кратчайших путей. Если к положить к — к 1 и вернуться к шагу 2.

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

Обоснование вышеприведенного алгоритма основано на очевидном факте [11], [20]: путь должен быть отклонением на этапе (при некотором от одного из более коротких путей Поэтому необходимо просто построить все кратчайшие отклонения от каждого из и просмотреть их для нахождения самого короткого отклонения. Это и будет путь Следует заметить, что при итерации все кратчайшие отклонения для к — 2, уже включены в и нужно найти только одно отклонение от и пополнить им имеющийся список.

На шаге 3 мы полагаем с для тех начальные подпути которых, содержащие вершин, совпадают с начальным -вершинным подпутем пути Это делается для того, чтобы не получить снова в качестве отклонения (в точке ) от пути что вполне могло случиться, если бы мы действовали иначе, Так как при вес пути не больше веса пути

Хотя на шаге 5 алгоритма каждый порожденйый путь и помещается в список совершенно очевидно, что на итерации этот список не должен содержать более К — к кратчайших отклонений С вычислительной точки зрения наиболее сложным является шаг 4, где требуется или операций в зависимости от того, будут ли все или Так как этот шаг при итерации выполняется раз и так как а число итераций равно К, то рассматриваемый алгоритм при нахождении кратчайших путей требует порядка или операций. Первая величина относится к графам с неотрицательными матрицами весов, а вторая — к графам с произвольными матрицами.