graph - 使用 Dijkstra 在有向图中找到负循环？

Question

我有一个带负边 (u,v) 的有向图 G=(v,e)。所有其他边都是正的。

如何使用 Dijkstra 找到负循环？

Answer 1

(u,v)从图中删除。v找到从到的最短路径u（使用 Dijkstra）。如果它的总重量小于-w(u,v)，那么你已经找到了负循环。否则不存在这样的循环。