Bellman-Ford算法中最短路径是否为简单路径？无负环时结论是否成立？

关于Bellman-Ford算法中最短路径的两个问题解答 #

问题1：Bellman-Ford算法中的最短路径是否为简单路径？ #

得分情况讨论：

• 如果图中不存在从源点s可达的负权环，那么从s到任意可达顶点t的最短路径一定是简单路径（即路径里没有重复顶点，最多包含n-1条边，n是图的顶点总数）——这也是Bellman-Ford算法只需要迭代n-1次就能找到最短路径的核心原因。
• 如果图中存在从s可达的负权环，那么对于环上的顶点以及能从环到达的顶点，不存在最短路径——因为你可以无限次绕负权环，路径总权值会无限减小，没有下限，而Bellman-Ford算法的核心作用之一就是检测这类负权环的存在。

问题2：“若图中不存在负环，从s到t的最短路径必定是简单路径”的观点是否正确？推理是否合理？ #

你的观点完全正确，而且推理逻辑非常严谨！

咱们再把你的推理细化验证一下：
假设存在一条从s到t的最短路径，其中重复出现了某个顶点v，那这条路径必然包含一个环：... → v → [环] → v → ...。

• 如果这个环的权值是非负的：直接去掉这个环后，得到的新路径s → ... → v → ... → t总权值不会比原路径大，甚至可能更小——这就和原路径是“最短路径”的前提矛盾了。
• 如果这个环的权值是负的：那这就是一个负权环，但题目里已经明确图中不存在负环，所以这种情况不可能发生。

因此，当图中没有负环时，最短路径里不可能存在重复顶点，必然是简单路径。你的推理完全站得住脚～

内容的提问来源于stack exchange，提问作者toxin9