Случай отрицательных циклов

Алгоритм Флойда-Уоршелла нахождения кратчайших путей между всеми парами вершин

Дан ориентированный или неориентированный взвешенный граф G с
n вершинами. Требуется найти значения всех величин D[i,j] — длины кратчайшего пути из вершины i в вершину j.

Предполагается, что граф не содержит циклов отрицательного веса (тогда ответа между некоторыми парами вершин может просто не существовать — он будет бесконечно маленьким).

Идея

Пробуем улучшить путь (существующий или несуществующий) между вершинами i и j через вершину k.

Реализация

На вход программе подаётся граф, заданный в виде матрицы смежности — двумерного массива D[i,j] размера , в котором каждый элемент задаёт длину ребра между соответствующими вершинами.

Требуется, чтобы выполнялось D[i, i]=0 для любых i.

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

d[i, j] = min (d[i, j], d[i, k] + d[k, j]);

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

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

const INF=maxlongint;

…

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (d[i, k] < INF) and (d[k, j] < INF)

d[i, j] = min (d[i, j], d[i, k] + d[k, j]);

Восстановление самих путей

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

Для этого достаточно кроме матрицы расстояний D[i, j] поддерживать также матрицу предков Pr[i,j], которая для каждой пары вершин будет содержать номер вершины k, через которую было получено кратчайшее расстояние между ними. Теперь нам просто надо найти кратчайший путь между вершинами i и Pr[i, j], а также между Pr[i, j] и j. Отсюда получается простой рекурсивный алгоритм восстановления кратчайшего пути.

Случай вещественных весов

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

Применительно к алгоритму Флойда неприятным спецэффектом этих погрешностей становится то, что найденные алгоритмом расстояния могут уйти сильно в минус из-за накопившихся ошибок. В самом деле, если на первой фазе имела место ошибка ∆, то на второй итерации эта ошибка уже может превратиться в 2∆, на третьей — в 4∆, и так далее.

Чтобы этого не происходило, сравнения в алгоритме Флойда следует делать с учётом погрешности:

if (d[i, k] + d[k, j] < d[i, j] - EPS)

d[i, j] = d[i, k] + d[k, j];

ВНИМАНИЕ!!! Значение EPS зависит от условия задачи. Например, если в задаче указано, что ваш ответ может отличаться от ответа жюри на 10³, то EPS=10⁴.

Случай отрицательных циклов

Если в графе есть циклы отрицательного веса, то формально алгоритм Флойда-Уоршелла неприменим к такому графу.

На самом же деле, для тех пар вершин i и j, между которыми нельзя зайти в цикл отрицательного вес, алгоритм отработает корректно.

Для тех же пар вершин, ответа для которых не существует (по причине наличия отрицательного цикла на пути между ними), алгоритм Флойда найдёт в качестве ответа какое-то число (возможно, сильно отрицательное, но не обязательно). Тем не менее, можно улучшить алгоритм Флойда, чтобы он аккуратно обрабатывал такие пары вершин и выводил для них, например, -∞.

Для этого можно сделать, например, следующий критерий "не существования пути". Итак, пусть на данном графе отработал обычный алгоритм Флойда. Тогда между вершинами i и j не существует кратчайшего пути тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется D[t, t]<0.

Кроме того, при использовании алгоритма Флойда для графов с отрицательными циклами следует помнить, что возникающие в процессе работы расстояния могут сильно уходить в минус. Поэтому следует принять меры против целочисленного переполнения, ограничив все расстояния снизу какой-нибудь величиной (например,
-INF).