Дистанционная подготовка: При чем тут алгоритм Флойда?
Re: При чем тут алгоритм Флойда?
от Данил Исрафилов - Воскресенье 5 Июль 2015, 11:09
  Алгоритм Флойда нужен здесь, потому что раздел так и называется. Для графов часто есть несколько решений, но по-практиковать нужно каждый.

Теперь про циклы с отрицательным весом (объяснение разбора):
Если в графе есть циклы отрицательного веса, то формально алгоритм Флойда-Уоршелла к такому графу неприменим. Но на самом деле алгоритм корректно сработает для всех пар, пути мужду которыми никогда не проходят через цикл негативной стоимости, а для остальных мы получим какие-нибудь числа, возможно сильно отрицательные. Алгоритм можно научить выводить для таких пар некое значение, соответствующее -∞
Кстати после отработки такого графа на диагонале матрицы кратчайших путей возникнут отрицательные числа — кратчайшее расстояние от вершины в этом цикле до неё самой будет меньше нуля, что соответствует проходу по этому циклу, так что алгоритм можно использовать для определения наличия отрицательных циклов в графе.

http://habrahabr.ru/post/105825/ - это ссылка на источник объяснения.

И вот еще что. По всей видимости (я не уверен, конечно), у автора алгоритм всегда проходится по массиву 60х60 вне зависимости от заданного размера. Чтобы не создавать лишних размеров, можно при а[i, j] = 0, присваивать a[i, j] = n - 1, где n - длина стороны массива, a при a[i, j] = 1, присваивать a[i, j] = -1, причем на главной диагонали все равно нужно всегда ставить нули, а не -1.