可以使用 Bellman-Ford 算法在只有正边的图上找到最短路径吗？
Can Bellman-Ford algorithm be used to find shorthest path on a graph with only positive edges?
我知道Dijkstra算法只能用于边的正长度，当图也有负长度时可以使用Bellman-Ford。
不过，假设我们有一个只有正边的图。 Bellman-Ford 会给出与 Dijkstra 相同的结果吗？
是的，它会给出相同的结果。不过，它会 运行 变慢，因为它也可以用于具有负边的图形（在没有负循环的情况下）。如果你看一下 BF 正确性的证明，那里没有假设某些边是负的。
我想对 Ami Tavory 的回答进行补充。 Bellman-ford 的算法可以做得更快一点，如果你能检测到在任何一次通过时，没有节点值更新，然后 return 从那里。如果没有节点更新则证明每次节点遍历完成。
我知道Dijkstra算法只能用于边的正长度，当图也有负长度时可以使用Bellman-Ford。
不过，假设我们有一个只有正边的图。 Bellman-Ford 会给出与 Dijkstra 相同的结果吗？
是的，它会给出相同的结果。不过，它会 运行 变慢，因为它也可以用于具有负边的图形（在没有负循环的情况下）。如果你看一下 BF 正确性的证明，那里没有假设某些边是负的。
我想对 Ami Tavory 的回答进行补充。 Bellman-ford 的算法可以做得更快一点，如果你能检测到在任何一次通过时，没有节点值更新，然后 return 从那里。如果没有节点更新则证明每次节点遍历完成。