知识卡片
最短路径松弛累计源点距离
初始化d[s]=0,其余为无穷;反复选择未确定顶点中d最小者u,对每条u→v边比较d[u]+w(u,v)与d[v],较小则更新距离和父指针。这里选择的是源点累计距离最小的顶点,不是单独选择边权最小的边;松弛是更新估计,不是释放内存。
图中a→c→f→b的权值4+1+2=7;a→c→e为8,a→c→f→b→d为9。非负边使已确定的最小距离不会被后续路径改善,负边则不能沿用这一保证。相同最短代价可以对应多条路径,parent只是某一种选择。
无穷必须大于所有有效路径代价,而不只大于每条边;无可达候选时应停下或明确保留不可达状态。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
非负数。与Prim算法一样,Dijkstra算法也是一种利用贪心算法计算并最终能够产生最优结果的算法。之所以说该算法使用了贪心算法,是因为它将当前看起来最短的边加入最短路径树中。 从根本上来说,Dijkstra算法通过选择一个顶点,并不断地探寻与此顶点相关的边,以此来确定每个顶点的最短路径是否是最优
参考来源
- 位置:《算法精解:C语言描述》第16章《Dijkstra算法》(spine1412;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1378.html;u297-ch16-009)。
- 结论依据:297全文及03083所有六阶段图、权重与父节点实读。
- 原始内容:非负数。与Prim算法一样,Dijkstra算法也是一种利用贪心算法计算并最终能够产生最优结果的算法。之所以说该算法使用了贪心算法,是因为它将当前看起来最短的边加入最短路径树中。 从根本上来说,Dijkstra算法通过选择一个顶点,并不断地探寻与此顶点相关的边,以此来确定每个顶点的最短路径是否是最优