78
правок
Изменения
м
→Нахождение отрицательного цикла
Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин <tex>(i, j)</tex>, в том числе и теми, у которых <tex>i = j</tex>, а начальное расстояние между парой вершин <tex>(i, i)</tex> равно нулю, то релаксация может произойти только при наличии вершины <tex> k </tex> такой, что <tex> d[i][k] + d[k][i] < 0 </tex>, что эквивалентно наличию отрицательного цикла, проходящего через вершину <tex> i </tex>.
}}
Из доказательства следует, что для поиска цикла отрицательного веса необходимо, после завершения работы алгоритма, найти вершину <tex> i </tex>, для которой <tex> d[i][i] < 0 </tex>, и вывести кратчайший путь между парой вершин <tex> (i, i) </tex>. При этом стоит учитывать, что при наличии отрицательного цикла расстояния могут уменьшаться экспоненциально. Для предотвращения переполнения все вычисления стоит ограничивать снизу величиной <tex>-INF</tex>, либо проверять наличие отрицательных чисел на главной диагонали во время подсчета.
== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
