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

 

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

 

Алгоритм

 

Инициализация структур данных

Построим матрицу D⁰ размерности |V| x |V|, элементы которой (обозначим из v) определяются по правилу:

1. d_ii⁰= 0;
2. d_ij⁰= Вес(v_i, v_j), где i<>j, если в графе существует ребро (дуга) (v_i, v_j);
3. d_ij⁰= бесконечность , где i<>j, если нет ребра (дуги) (v_i, v_j).

Основная часть алгоритма:

 

§         Выполнять цикл, завершение которого наступает по выполнению одного из двух условий: либо количество шагов цикла равно V, либо был обнаружен цикл отрицательной длины. Шаги цикла нумеруются с нуля. Шаг цикла будем обозначать переменной m.

o       Строится матрица с индексом равным номеру шага, обозначим его через m, в которой элементы определяются через элементы матрицы предыдущего шага по следующим формулам: d_ij^m+1=min{d_ij^m, d_i(m+1)^m + d_(m+1)j^m}, где i<>j; d_ii^m+1=0.

o       Если d_im^m + d_mi^m < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину v_i;

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

Поиск путей

Если требует найти сами пути, то перед началом работы алгоритма построим матрицу P с начальными значениями элементов p_ij=i. Каждый раз, когда на шаге (1) значение d_ij^m+1 будет уменьшаться в соответствии с (*) (т.е. когда d_i(m+1)^m + d_(m+1)j^m<d_ij^m), выполним присваивание p_ij:=p_(m+1)j. В конце работы алгоритма матрица P будет определять кратчайшие пути между всеми парами вершин: значение p_ij будет равно номеру предпоследней вершины в пути между i и j (либо p_ij=i, если путь не существует).

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