Математика : Графы.

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

Дано: непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кpатчайших пyтей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.

Инициализация:

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

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

Основная часть:

1. Построим матрицу D^m+1 по D^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 (*).
Если d_im^m + d_mi^m < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину v_i; ВЫХОД.

2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D^|V| равны длинам кратчайших путей между соответствующими вершинами; ВЫХОД.

КОНЕЦ

Если требует найти сами пути, то перед началом работы алгоритма построим матрицу 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 являются симметричными, поэтому достаточно вычислять элементы, находящиеся только выше (либо только ниже) главной диагонали.

Вверх по странице, к оглавлению и навигации.