咱们用反证法来推导这个结论，逻辑会非常直观：

1. 先明确核心前提：图中不存在负权环

   • 首先，最短路径不可能包含任何环——如果路径里有一个环，因为没有负权环，这个环的总权值要么是正的，要么是0。如果是正权环，去掉这个环后路径总权值会更小，和“这是最短路径”矛盾；如果是零权环，去掉环后路径长度不变，但路径边数更少，同样说明原路径不是最优的。所以最短路径一定是不含重复顶点的简单路径。

2. 分析简单路径的边数上限

   • 图中总共有n个顶点，一条简单路径（不含重复顶点）最多能包含多少个顶点？答案是n个（每个顶点恰好出现一次）。
   • 每一条边连接两个不同的顶点，所以n个顶点的简单路径，边数必然是n-1条（比如顶点序列s→v₁→v₂→…→t，总共有n个顶点的话，中间有n-1条边）。

3. 假设与矛盾推导

   • 假设存在一条从s到t的最短路径，其边数≥n。那这条路径包含的顶点数就是边数+1≥n+1个。
   • 根据鸽巢原理，n+1个顶点放进n个不同的顶点集合里，必然至少有一个顶点被重复访问，也就意味着这条路径里存在环。
   • 但我们第一步已经证明了最短路径不可能包含环，这就和假设矛盾了。

综上，当图中不存在负权环时，从s到t的每条最短路径的边数最多为n-1。

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