社区讨论

关于Dijkstra求次短路 更新次短路的正确性的一点疑问

P2865[USACO06NOV] Roadblocks G参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo28ld7b
此快照首次捕获于
2023/10/23 09:46
2 年前
此快照最后确认于
2023/11/16 09:39
2 年前
查看原帖
这题在跑dijkstra用一个点u去松弛其他点的时候,如果u能更新其相邻点v的最短路,似乎大部分题解的思路都是直接把v的次短路更新成其原来的最短路,然后更新v的最短路,没有管u的次短路,但是是否有可能u的次短路可以去更新v的次短路呢?即u的次短路加上这条边得到的长度介于v点原来的最短路和更新后的最短路之间,这样用u的次短路更新的出来的v的次短路就会比前面那种更新方式得到的v的次短路小,如何证明只用前面那种更新方式的正确性呢?

回复

2 条回复,欢迎继续交流。

正在加载回复...