Алгоритм Флойда

   Алгоритм последовательно перебирает все такие 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

подробнее про поиск отрицательного цикла можно почитать здесь: http://e-maxx.ru/algo/export_ford_bellman

Путь проходящий через цикл отрицательного веса становится невозможным.