algorithm - SPFA アルゴリズムを使用した負のサイクルの検出

Question

負の重みと正の重みを持つ有向グラフで以下の SPFA アルゴリズムを使用すると、どのように負のサイクルを検出できますか?

手順 Shortest-Path-Faster-Algorithm(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