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

Задача нахождения отрицательного циклв тесно связана с задачей нахождения кратчайшего пути. Существование отрицательных стоимостей ребер делает решение задачи нахождения отрицательных циклов или вычисления дерева кратчайших путей более сложной и требует больше времени по сравнению с решением задачи нахождения дерева кратчайших путей в орграфах с неотрицательными стоимостями ребер. В качестве примера можно рассмотреть орграфы с вещественными стоимостями ребер и сравним алгоритм с временем исполнения O(nm) для первого случая с алгоритмом с временем O(m + nlog n) для второго (алгоритмом Дейкстры, реализованным с эффективной очередью с приоритетами; см., например, [1]).

Единственный случай, когда обе временные сложности совпадают, касается орграфов с малой древесной шириной [ ]; в результате этот класс графов в настоящий момент является классом самого общего вида. Для планарных орграфов результат, приведенный в [3], только на полилогарифмический коэффициент отличается от алгоритма с временем исполнения O(n), вычисляющего дерево кратчайших путей в случае неотрицательной стоимости ребер.