算法第4版 4.4.3 最优路径算法的理论基础 最短路径的最优条件描述是不是不太准确?
当且仅当对于从v到w的任意一条边e,这些值都是满足disTo[w]<=distTo[v] + e.weight()
时(换句话说,就是不存在有效边时),它们是最短路径。
刚开始我是这么理解w、v和e的
后来才明白应该是这样
你理解的没错,但是我觉得你可能想复杂了,我感觉这一段就是解释和证明数组 distTo[v] 保存的是从 s 到 v 的最短距离, v 和 w 都不是定值,disTo[w]<=distTo[v] + e.weight() 的意思就是指到节点 w 的最短距离不可能比经由其他节点去往 w 的距离更长。
附上英文原版帮助理解: