列出有向图中的所有负循环

Question

对于具有负权重的有向图 G(V,E)，我搜索了一些类似的主题，似乎贝尔曼福德可以检测负循环。但是一旦发现负循环就停止了，那么在这种情况下我们如何列出所有负循环呢？

考虑到埃里克·利珀特的建议，我尝试删除从图中发现的负循环，但我觉得这是不正确的，为什么？因为循环被删除后图形会发生变化，并且旧图形中可能存在额外的非负循环，但在新图形中不会找到。有人可以帮助我理清这个问题吗？

这可以用 java 或 c# 实现（不过我更喜欢 c#）

谢谢

Answer 1

好吧，你当然无法有效地找到它们：考虑n每条边的权重为负 -1 的顶点的完整图。该图中存在指数数量的负权重循环，因此将它们全部写下来需要指数时间！

如果这并没有阻止您，那么您最好的选择是应用任何旧的循环查找算法，例如本问题中的算法来查找所有循环，然后丢弃那些具有非负权重的循环。