7.3 松弛操作

liweiwei1419 ... 2021-12-11 图论
  • Dijkstra
Less than 1 minute

提示

请注意松弛操作成立的前提是「没有负权边」。

  • 0 -> 2 这条路径,就是从顶点 0 到顶点 2 的最短路径。由于没有负权边,因此不会有一条边,我们绕道走回到顶点 2,路径之和更小

事实上,从 0 到 1 ,我们经过 2 再来到 1 ,路径之和 2+1<52 + 1 < 5,这就是松弛操作的意义。就像我们坐飞机,有的时候经停,费用可能更低。

再次理解松弛操作:5522 大,55 加上一个非负整数不可能比 22 还小。

Last update: January 14, 2022 10:18
Contributors: suanfa8 , liweiwei1419