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

В случае орграфов общего вида лучшим алгоритмом для решения задачи нахождения отрицательного цикла (или вычисления дерева кратчайших путей в случае, если такого цикла не существует) является классический [[алгоритм Форда|алгоритм Беллмана-Форда]] с временем исполнения 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> и основанный на битовом масштабировании.

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

Для разреженных орграфов общего вида в [8] был предложен алгоритм для решения задачи нахождения отрицательного цикла за время <math>O(n + \tilde{ \gamma } ^{1.5} log \; \tilde{ \gamma } )</math>, где <math>\tilde{ \gamma } \;</math> – топологическая мера входного разреженного орграфа G, значение которой меняется от 1 до <math>\Theta (n) \;</math>. Неформально <math>\tilde{ \gamma } \;</math> представляет минимальное количество внешнепланарных подграфов, удовлетворяющих определенным свойствам отделимости и полученных в результате декомпозиции графа G. В частности, <math>\tilde{ \gamma } \;</math> пропорционально <math>\gamma (G) + q \;</math>, где G предполагается вложенным в ориентируемую поверхность рода <math>\gamma (G) \;</math> таким образом, чтобы минимизировать количество q граней, совместно покрывающих все вершины. Например, если граф G является внешнепланарным, то <math>\tilde{ \gamma } = 1 \;</math>, в результате для такого случая получаем оптимальный алгоритм с временем исполнения O(n). Алгоритм в [8] не требует необходимого наличия такого вложения входного графа. В той же статье показано, что случайные графы <math>G_{n,p} \;</math> с пороговой функцией 1/n являются планарными с вероятностью 1, а ожидаемое значение <math>\tilde{ \gamma } \;</math> для них равно O(1). Кроме того, в [8] предложено эффективное распараллеливание алгоритма на базе модели вычислений CREW PRAM.

Для планарных орграфов получены лучшие границы. Для случая, когда стоимости ребер являются целыми числами, в [9] предложен алгоритм с временем исполнения <math>O(n^{4/3} \; log (nL))</math>. В случае ребер с вещественными значениями стоимости алгоритм с временем исполнения <math>O(n \; log^3 \; n)</math> можно найти в работе [5].

Для случая орграфов с малой древесной шириной (и вещественными значениями стоимости ребер) в [3] предложен оптимальный алгоритм с временем исполнения O(n). Неформально древесная ширина t графа G представляет собой параметр, измеряющий, насколько структура G близка к структуре дерева. К примеру, класс графов с малой древесной шириной включает [[серийно-параллельный граф|серийно-параллельные графы]] (t = 2) и [[внешнепланарный граф|внешнепланарные графы]] (t = 2). Оптимальный параллельный алгоритм решения той же задачи на базе модели вычислений CREW PRAM был предложен в [2].

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

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