graph-theory - 使用 Bellman Ford 进行负循环检测是否取决于起始节点的选择？

Question

我一直在做以下问题CSES 问题：循环查找，它要求我在有向图中查找并打印负循环。Bellman Ford 可以解决这个问题，但我观察到 1-2 个测试用例（总共 18 个）总是失败，具体取决于起始节点的选择。

这是否意味着在有向图中，贝尔曼福特受制于起始节点的选择？ 因为我在无向图中没有遇到类似的问题。

考虑以下测试用例： 如果我从 1 开始，我不会检测到负循环。但是，如果我从 3 开始，我可以检测到它。该怎么办 ？

标签： graph-theorygraph-algorithmshortest-pathgraph-traversalbellman-ford

Answer 1

如果负环可以从起始节点到达，Bellman Ford 算法将检测它们。在无向连通图中，我们没有这个问题，因为所有节点都可以从任何节点到达。为了在有向图中解决这个问题，我们可以添加一个节点并使用权重为 0 的有向边将其连接到所有其他节点。它不会创建任何新循环。这种方法也用于约翰逊算法中的所有对最短路径问题。