Дан ориентированный или неориентированный взвешенный граф с n вершинами.
Алгоритм позволяет найти расстояние от каждой до каждой вершины и работает с отрицательными ребрами.
 Алгоритм последовательно перебирает все такие I, через которые может лежать более короткий путь в V, чем который имеется сейчас.
Текущий (синий) путь и потенциально более короткий (красный).
Реализация
На вход программе подаётся граф, заданный в виде матрицы смежности — двумерного массива d[][] размера n х n, в котором каждый элемент задаёт длину ребра между соответствующими вершинами.
Предполагается, что если между двумя какими-то вершинами нет ребра, то в матрице смежности было записано какое-то большое число ( например INT_MAX в "limits.h", чтобы оно было больше длины любого пути в этом графе); тогда это ребро всегда будет невыгодно брать, и алгоритм сработает правильно.
Но при сложении двух бесконечностей может получиться переполнение int и на выходе будем иметь какое то отрицательно значение, поэтому неплохо бы подстраховаться дополнительной проверкой:
if (d[i][k] < INT_MAX && d[k][j] < INT_MAX)
В итоге алгоритм будет иметь вид:
for (int k=0; k<n; ++k)
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (d[i][k] < INT_MAX && d[k][j] < INT_MAX)
if(d[i][k]+d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
Например, дан граф:
Тогда начальная весовая матрица будет:
| номера вершин |
1 |
2 |
3 |
| 1 |
0 |
8 |
5 |
| 2 |
3 |
0 |
INT_MAX |
| 3 |
INT_MAX |
2 |
0 |
после 1-ой итерации:
| номера вершин |
1 |
2 |
3 |
| 1 |
0 |
8 |
5 |
| 2 |
3 |
0 |
8 |
| 3 |
INT_MAX |
2 |
0 |
после 2-ой итерации:
| номера вершин |
1 |
2 |
3 |
| 1 |
0 |
8 |
5 |
| 2 |
3 |
0 |
8 |
| 3 |
5 |
2 |
0 |
после 3-ей итерации:
| номера вершин |
1 |
2 |
3 |
| 1 |
0 |
7 |
5 |
| 2 |
3 |
0 |
8 |
| 3 |
5 |
2 |
0 |
|
|
|
Если в графе есть циклы отрицательного веса, то формально алгоритм Флойда-Уоршелла неприменим к такому графу.
На самом же деле, для тех пар вершин i и j, между которыми нельзя зайти в цикл отрицательного вес, алгоритм отработает корректно.
Для тех же пар вершин, ответа для которых не существует (по причине наличия отрицательного цикла на пути между ними), алгоритм Флойда найдёт в качестве ответа какое-то число (возможно, сильно отрицательное, но не обязательно). Тем не менее, можно улучшить алгоритм Флойда, чтобы он аккуратно обрабатывал такие пары вершин и выводил для них, например, \(- \infty\).
Для этого можно сделать, например, следующий критерий "не существования пути". Итак, пусть на данном графе отработал обычный алгоритм Флойда. Тогда между вершинами i и j не существует кратчайшего пути тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется \(d[t][t]<0\).
Кроме того, при использовании алгоритма Флойда для графов с отрицательными циклами следует помнить, что возникающие в процессе работы расстояния могут сильно уходить в минус, экспоненциально с каждой фазой. Поэтому следует принять меры против целочисленного переполнения, ограничив все расстояния снизу какой-нибудь величиной (например, \(- \infty\)).
Словесно решение можно описать таким образом:
После того, как алгоритм Флойда-Уоршелла отработает для входного графа, переберём все пары вершин \((i,j)\), и для каждой такой пары проверим, бесконечно мал кратчайший путь из i в j или нет. Для этого переберём третью вершину t, и если для неё оказалось \(d[t][t] < 0\) (т.е. она лежит в цикле отрицательного веса), а сама она достижима из i и из неё достижима j — то путь \((i,j)\) может иметь бесконечно малую длину.
|
Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин (i,j), в том числе и теми, у которых i=j, а начальное расстояние между парой вершин (i,i) равно нулю, то релаксация может произойти только при наличии вершины k такой, что d[i][k]+d[k][i]<0, что эквивалентно наличию отрицательного цикла, проходящего через вершину i
|
|
|
Путь проходящий через цикл отрицательного веса становится невозможным.
|