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

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

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