小编meh*_*tin的帖子

在具有负权重和正权重的有向图中使用下面的 SPFA 算法，我们如何检测负循环？

程序最短路径更快算法(G, s)

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