Самый быстрый алгоритм для определения наличия отрицательного цикла на графике

Question

Я использую матрицу d представить график. d.(i).(j) означает расстояние между i а также j; v обозначает количество узлов в графе.

Возможно, что в этом графике есть отрицательный цикл.

Я хотел бы проверить, существует ли отрицательный цикл. Я написал что-то из вариации Флойд-Варшалл следующим образом:

let dr = Matrix.copy d in

(* part 1 *)
for i = 0 to v - 1 do
  dr.(i).(i) <- 0
done;

(* part 2 *)
try
  for k = 0 to v - 1 do
    for i = 0 to v - 1 do
      for j = 0 to v - 1 do
          let improvement = dr.(i).(k) + dr.(k).(j) in  
          if improvement < dr.(i).(j) then (
          if (i <> j) then
            dr.(i).(j) <- improvement
          else if improvement < 0 then
            raise BreakLoop )
      done
    done
  done;
  false
with 
  BreakLoop -> true

Мои вопросы

1. Правильный ли приведенный выше код?
2. Это part 1 полезно?

Поскольку я вызываю эту функцию очень часто, я действительно хочу сделать ее как можно быстрее. Так что мой 3) вопрос, если другие алгоритмы (особенно Bellman-Ford) может быть быстрее, чем это?

Answer 1

Первый вопрос о правильности вашего кода больше подходит для http://codereview.stackexchange.com/.

---

Для этой проблемы подходит либо Bellman-Ford, либо Floyd-Warshall. Сравнение производительности следует:

• Беллман-Форд (Википедия)
  • Время-сложность: O(|V|*|E|)
  • Пространственно-сложность: O(|V|)
  • Раздел "Поиск отрицательных циклов" - это то, что вы хотите
• Флойд-Варшалл (Википедия)
  • Время-сложность: O(|V|^3)
  • Пространственно-сложность: O(|V|^2)

поскольку |E| ограничен |V|^2 Bellman-Ford - явный победитель, и я бы посоветовал вам его использовать.

---

Если графы без отрицательных циклов являются ожидаемым нормальным случаем, может быть целесообразно сделать быструю проверку в качестве первого шага вашего алгоритма: содержит ли граф отрицательные ребра? Если нет, то он, конечно, не содержит никаких отрицательных циклов, и у вас есть O(|E|) алгоритм наилучшего случая для обнаружения наличия любых отрицательных циклов.

Answer 2

Хотя все варианты, перечисленные в ответе Тимоти Шилда, являются правильными алгоритмами для поиска отрицательного цикла в ориентированном взвешенном графе, они не самые быстрые.

В данном случае я всегда использую алгоритм кратчайшего пути и быстрее.

Хотя у него есть временная сложность наихудшего случая O(|V|*|E|), который совпадает с Bellman-Ford, очень мало графиков, для которых SPFA действительно достигает этого времени. На практике это происходит намного быстрее, даже при достижении (недоказанного) среднего времениO(|E|).

Я написал статью в своем блоге, в которой объясняются детали использования SPFA для поиска отрицательных циклов.

Если вы не хотите читать статью полностью, ниже указан нужный вам псевдокод.

function SPFA(G):
    for v in V(G):
        len[v] = 0
        dis[v] = 0
        Queue.push(v)
    while !Queue.is_empty():
        u = Queue.pop()
        for (u, v) in E(G):
            if dis[u] + w(u, v) < dis[v]:
                len[v] = len[u] + 1
                if len[v] == n:
                    return "negative cycle detected"
                dis[v] = dis[i] + w(u, v)
                if !Queue.contains(v):
                    Queue.push(v)
    return "no negative cycle detected"