2.3 .Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда).

Процедура находит пути минимального веса в графе G = (V, E) заданном весовой матрицей W у которой элемент wij  равен весу ребра соединяющего i-ую и j-ую вершины. При этом полагаем, что wii  = 0 для всех i. Путь ищется для всех пар вершин графа. Для задания веса равного бесконечности используется число GM, его можно задавать в зависимости от конкретной задачи.

Следует заметить, что если в графе существует контур отрицательной суммарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае, описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее, надо заметить, что если граф неориентированный (W симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать, пока не сделаем вес достаточно малым).

Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы dij  которые представляют из себя вес минимального пути соединяющего i и j вершины. Рассмотрим преобразования матрицы весов:

D0  = W

dm+1 [i, j] = min{dm [i, j], dm [i, m+1] + dm [m+1, j]}, i != j

dm+1 [i, i] = 0

преобразование проделывается для m = 1, ..., n, где n - мощность множества вершин графа. Если на некотором шаге получим отрицательное dm [i, m]+dm [m, i] для какого-нибудь i, то в графе существует контур отрицательного веса, проходящий через вершину i и задача не разрешима.

На выходе получаем матрицу D минимальных весов и матрицу P при помощи, которой можно восстановить путь минимального веса следующим образом: значение p[i, j] будет равно номеру предпоследней вершины в пути между i и j (либо p[i, j] равно i, если путь не существует). Переменная s на выходе равна единице, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.

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

К сожалению, для данного алгоритма нет исходного кода. Это не ошибка и сообщать мне об этом не надо. Возможно, для алгоритма ещё не успели создать исходный код, или же при переносе алгоритма из старой версии библиотеки возникли проблемы с исходником и его написание пришлось отложить до лучших времен. Попробуйте воспользоваться прилагаемыми файлами и блок-схемой или поискать на сайте аналогичный алгоритм, но с исходником.