algorithm - 证明Dijkstra算法的修改

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗Update the question所以堆栈溢出的值小于aa>。
在dijkstra算法中，我们计算路径长度以找到最短路径。Dijkstra算法的常规版本将路径长度计算为某个节点v上的权重之和。
如果路径长度被计算为高达v的最大长度的总和遍历到v？
我已经在纸上做了练习，发现它仍然有效但我怎么证明呢？
我们将非常感谢您的帮助

最佳答案

如果说“仍然有效”，你的意思是它会产生相同的最短路径，下面是一个反例：

B --1-- C -- 1 -- D
|                 |
1                 1
|                 |
S --3-- A ----1----

仅使用路径长度，从s到a的最短路径将通过s到a的边。
路径长度+最大权重，最短路径为S到B到C到D到A（权重5）。S到A的重量是6。

关于algorithm - 证明Dijkstra算法的修改，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21193240/