78
правок
Изменения
Нахождение отрицательного цикла
print v
== Нахождение отрицательного цикла ==
{{Утверждение
|statement=
При наличии цикла отрицательного веса в матрице <tex> D </tex> появятся отрицательные числа на главной диагонали.
|proof=
Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин <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>.
== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
