Обнаружение отрицательных циклов с использованием алгоритма SPFA

Используя алгоритм SPFA ниже в ориентированном графе с отрицательным и положительным весами, как мы можем обнаружить отрицательные циклы?Обнаружение отрицательных циклов с использованием алгоритма SPFA

процедура кратчайшего пути-Faster-алгоритм (G, s)

1 for each vertex v ≠ s in V(G) 
    2  d(v) := ∞ 
    3 d(s) := 0 
    4 push s into Q 
    5 while Q is not empty 
    6  u := pop Q 
    7  for each edge (u, v) in E(G) 
    8   if d(u) + w(u, v) < d(v) then 
    9    d(v) := d(u) + w(u, v) 
10    if v is not in Q then 
11     push v into Q

источник

2013-08-02 mehmetin

Из [доказательство правоты] (http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm#Proof_of_correctness): «Алгоритм не может завершиться, если циклы отрицательного веса достижимы из источника ». Это именно то, что вы ожидаете, учитывая указанный псевдокод. Отсутствует условие завершения, отличное от очереди, становящейся пустой, что никогда не произойдет, когда встретится цикл отрицательного веса. Если вы хотите ввести такое условие, вы, вероятно, в конечном итоге сделаете что-то вроде «делает ли n-й раунд релаксацией?» проверка алгоритма Беллмана-Форда. –

Итак, мы должны проверить, ослаблен ли какой-либо из узлов n раз? – mehmetin

Я не очень тщательно проверил эту идею, но, возможно, можно было бы отслеживать предшественника каждого узла и проверять каждую операцию очереди n/log n, имеет ли график предшественников цикл. –

SPFA помещает новые узлы в очереди каждый раз, когда он видит «лучше» край, чтобы минимизировать общее расстояние, которое просто Беллман-Форд с лучшей обрезкой. Алгоритм Беллмана-Форда доказал, что циклы с отрицательным весом имеют максимум | V | - 1 ребра.

Таким образом, чтобы проверить, является ли цикл отрицательно взвешенным, вам просто нужно проверить, используете ли вы как минимум | V | ребра во время пробега вашего SPFA. Другими словами, проверьте, посетили ли вы один и тот же узел как минимум | V | раз.

Вот прилагается псевдокод:

procedure SPFA(G, s) 
    for each vertex v ≠ s in V(G) 
     d(v) := ∞ 
     visits(v) := 0 
    d(s) := 0 
    push s into Q 
    while Q is not empty 
     u := pop Q 
     visits(u) := visits(u) + 1      // increment visit count 
     if visits(u) < |V| then       // relaxation step 
      for each edge (u, v) in E(G) 
       if d(u) + w(u, v) < d(v) then 
        d(v) := d(u) + w(u, v) 
        if v is not in Q then 
         push v into Q

Однако, обратите внимание, что это не будет получать все узлы, которые являются частью отрицательного веса цикла. Чтобы получить все узлы, которые являются частью циклов отрицательного веса, сделайте DFS или BFS, чтобы отметить все узлы, достижимые от u, где посещений (u) = | V |.

Вот окончательный модифицированный псевдокод:

procedure DFS(G, u, visited) 
    if visited(u) = false then 
     visited(u) := true 
     for each edge (u, v) in E(G) 
      DFS(G, v, visited) 

procedure SPFA(G, s) 
    for each vertex v ≠ s in V(G) 
     d(v) := ∞ 
     visits(v) := 0 
    d(s) := 0 
    push s into Q 
    while Q is not empty 
     u := pop Q 
     visits(u) := visits(u) + 1      // increment visit count 
     if visits(u) < |V| then       // relaxation step 
      for each edge (u, v) in E(G) 
       if d(u) + w(u, v) < d(v) then 
        d(v) := d(u) + w(u, v) 
        if v is not in Q then 
         push v into Q 
    for each vertex u in V(G) 
     visited(u) := false 
    for each vertex u in V(G), where visits(u) = |V| 
     DFS(G, u, visited) 
    for each vertex u in V(G), where visited(u) = true 
     d(u) := -∞

источник

2014-11-06 03:35:44

Обнаружение отрицательных циклов с использованием алгоритма SPFA

ответ

Смежные вопросы