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

В случае орграфов общего вида лучшим алгоритмом для решения задачи нахождения отрицательного цикла (или вычисления дерева кратчайших путей в случае, если такого цикла не существует) является классический алгоритм Беллмана-Форда с временем исполнения O(nm) (см, например, [1]). Другие алгоритмы с той же временной сложностью приводятся в [4, 7, 12, 13]. Кроме того, в [11, глава 7] описано расширение алгоритма Беллмана-Форда, которое помимо обнаружения существующих отрицательных циклов и вывода их (при наличии) строит дерево кратчайших путей с корнем в некоторой вершине s, достигающих такие вершины u, у которых кратчайшие пути s-u не содержат отрицательного цикла. Для случая, когда стоимости дуг являются целыми числами не менее <math>- L (L \ge 2) \;</math>, в [6] предложен более оптимальный алгоритм, исполняющийся за время <math>O(m \sqrt{n} log \; L)</math> и основанный на битовом масштабировании.