7.3 松弛操作
liweiwei1419 ... 2021-12-11 Less than 1 minute
提示
请注意松弛操作成立的前提是「没有负权边」。
- 0 -> 2 这条路径,就是从顶点 0 到顶点 2 的最短路径。由于没有负权边,因此不会有一条边,我们绕道走回到顶点 2,路径之和更小。
事实上,从 0 到 1 ,我们经过 2 再来到 1 ,路径之和 ,这就是松弛操作的意义。就像我们坐飞机,有的时候经停,费用可能更低。
再次理解松弛操作: 比 大, 加上一个非负整数不可能比 还小。