社区讨论
关于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 条回复,欢迎继续交流。
正在加载回复...