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

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

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

1. d_ii⁰= 0;
2. d_ij⁰= Weight(v_i, v_j), где i<>j, если в графе существует ребро (дуга) (v_i, v_j);
3. d_ij⁰= -1 , где 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 < n, то повторяем шаг (1), иначе элементы последней построенной матрицы D^|n| равны длинам кратчайших путей между соответствующими вершинами; ВЫХОД.

КОНЕЦ