meh*_*tin 5 algorithm path cycle shortest
在具有负权重和正权重的有向图中使用下面的 SPFA 算法，我们如何检测负循环？
\n\n程序最短路径更快算法(G, s)
\n\n 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小智 6
每次看到“更好”的边缘时，SPFA 都会将新节点放入队列中，以最小化总距离，这只是贝尔曼-福特的更好修剪。Bellman-Ford 算法已经证明非负加权循环的最大值为|V| - 1 个边缘。
\n\n因此，要检查循环是否为负权重，您只需检查是否至少使用了|V| SPFA 运行期间的边缘。换句话说，检查您是否至少访问过同一个节点|V| 次。
\n\n这是附加的伪代码：
\n\nprocedure SPFA(G, s)\n for each vertex v \xe2\x89\xa0 s in V(G)\n d(v) := \xe2\x88\x9e\n visits(v) := 0\n d(s) := 0\n push s into Q\n while Q is not empty\n u := pop Q\n visits(u) := visits(u) + 1 // increment visit count\n if visits(u) < |V| then // relaxation step\n for each edge (u, v) in E(G)\n if d(u) + w(u, v) < d(v) then\n d(v) := d(u) + w(u, v)\n if v is not in Q then\n push v into Q\n但是，请注意，这不会获得属于负权重循环的所有节点。要获取属于负权重循环的所有节点，请执行 DFS 或 BFS 来标记从u可到达的所有节点，其中 Visits( u ) = |V| 。
\n\n这是最终修改后的伪代码：
\n\nprocedure DFS(G, u, visited)\n if visited(u) = false then\n visited(u) := true\n for each edge (u, v) in E(G)\n DFS(G, v, visited)\n\nprocedure SPFA(G, s)\n for each vertex v \xe2\x89\xa0 s in V(G)\n d(v) := \xe2\x88\x9e\n visits(v) := 0\n d(s) := 0\n push s into Q\n while Q is not empty\n u := pop Q\n visits(u) := visits(u) + 1 // increment visit count\n if visits(u) < |V| then // relaxation step\n for each edge (u, v) in E(G)\n if d(u) + w(u, v) < d(v) then\n d(v) := d(u) + w(u, v)\n if v is not in Q then\n push v into Q\n for each vertex u in V(G)\n visited(u) := false\n for each vertex u in V(G), where visits(u) = |V|\n DFS(G, u, visited)\n for each vertex u in V(G), where visited(u) = true\n d(u) := -\xe2\x88\x9e\n