有向图最短路径问题求证：为何无需包含图中最小权值边

构造反例 #

我们直接建一个无环的有向图：

• 节点集合：{s, a, t}
• 边集合（边权互异且非负）：
  • s → t，权值为3
  • s → a，权值为1（这是图中最小权值的边）
  • a → t，权值为3

计算s到t的路径：

• 直接路径s→t的总权值是3
• 经过最小边的路径s→a→t总权值是1+3=4

显然最短路径是s→t，完全不包含图中最小权值的边。

关于环的疑问 #

这个反例里没有任何环，说明结论错误和环的存在无关。本质原因是：图中的最小权值边可能属于“绕远路”的分支，把它加入路径后，总权值反而比不经过它的路径更大，自然不会出现在最短路径里。

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