Отрицательные циклы во взвешенных орграфах: различия между версиями

Задача нахождения отрицательного цикла тесно связана с задачей [[поиск кратчайшего пути|нахождения кратчайшего пути]]. В последней необходимо найти путь с минимальной стоимостью между двумя вершинами s и t. Легко увидеть, что кратчайший путь s-t существует в том и только том случае, если ни один путь s-t в графе G не содержит отрицательного цикла [1, 13]. Также известно, что все кратчайшие пути от заданной вершины s до всех других вершин формируют дерево, называемое [[дерево кратчайших путей|деревом кратчайших путей]] [1, 13].