关于Dijkstra求次短路 更新次短路的正确性的一点疑问
查看原帖
关于Dijkstra求次短路 更新次短路的正确性的一点疑问
642544
makerY楼主2023/7/13 23:02

这题在跑dijkstra用一个点u去松弛其他点的时候,如果u能更新其相邻点v的最短路,似乎大部分题解的思路都是直接把v的次短路更新成其原来的最短路,然后更新v的最短路,没有管u的次短路,但是是否有可能u的次短路可以去更新v的次短路呢?即u的次短路加上这条边得到的长度介于v点原来的最短路和更新后的最短路之间,这样用u的次短路更新的出来的v的次短路就会比前面那种更新方式得到的v的次短路小,如何证明只用前面那种更新方式的正确性呢?

2023/7/13 23:02
加载中...