2.2. Случай общей матрицы весов

Только что описанный алгоритм Дейкстры применим лишь в том случае, когда для всех Однако если матрица С является матрицей стоимостей, то дуги, приносящие доход, должны иметь отрицательные «стоимости». В этом случае для нахождения кратчайших путей между вершиной и всеми другими вершинами можно воспользоваться описанной ниже процедурой. Этот метод также является итерационным и основан на пометках вершин, причем в конце итерации пометки равны длинам тех кратчайших путей (от ко всем остальным вершинам), которые содержат не более к дуг. В отличие от алгоритма Дейкстры никакая из пометок во время этого процесса не рассматривается как окончательная. Описываемый метод был первоначально предложен в середине 50-х годов Фордом [14], Муром [26] и Веллманом [2]. Перейдем к его описанию.

2.2.1. Алгоритм для общей матрицы весов

Пусть пометка вершины в конце итерации.

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

Шаг 1. Положим для всех и для всех остальных

Обновление пометок

Шаг 2. Для каждой вершины изменить ее пометку следующим образом:

где (Множество S содержит теперь все вершины, для которых кратчайшие пути из состоят из к дуг.)

Множество содержит те вершины, для которых текущие кратчайшие пути из состоят из к дуг (т. е. те, вершины которых лежат в и для которых существуют дуги к вершине Отметим, что если то кратчайший путь от не может состоять из к дуг и поэтому изменять пометку вершины не нужно. Для вершин положим

Проверка на окончание

Шаг Если к для всех то получен оптимальный ответ и пометки равны длинам кратчайших путей. Останов.

(б) Если для некоторой вершины то перейти к шагу 4.

(в) Если для некоторой вершины то в графе существует цикл отрицательного веса и задача не имеет решения. Останов.

Подготовка к следующей итерации

Шаг 4. Обновить множество следующим образом:

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

Шаг 5. Положить и перейти к шагу 2.

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

Доказательство того, что приведенный алгоритм дает оптимальное решение, весьма простое. Здесь мы его не приводим.

Однако заметим, что оно базируется на принципе динамического программирования и том факте, что если не существует никакого оптимального пути из к дуг, то не может также существовать и никакого оптимального пути, содержащего к дуг [4]. Описанный алгоритм можно применять и в случае неотрицательной матрицы весов, хотя это, вообще говоря, намного хуже, чем использование алгоритма Дейкстры. В случае полного связного графа с вершинами этот алгоритм требует порядка операций сложения и сравнения, в то время как в алгоритме Дейкстры требуется операций. Некоторые улучшения описанного алгоритма, предложенные Йеном, позволяют уменьшить число операций в четыре раза, но порядок роста остается равным трем.

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

Рис. 8.3. Граф из примера 2.2.2.

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

Алгоритм работает следующим образом.

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

(см. скан)

(см. скан)

(см. скан)

Четвертая итерация

Шаг 2.

Вектор пометок равен

Шаг 4.

Пятая итерация

Шаг 2.

Шаг 3 (а). Останов.

Вектор пометок совпадает с следовательно, пометки равны длинам кратчайших путей.

Рис. 8.4. Окончательные пометки вершин и -бааа.

Сами пути строятся последовательно, как и в том случае, когда использовалось соотношение (8.2). Соответствующая -база показана жирными линия на рис. 8.4.