知识卡片

普通读书笔记卡 · 3644.h.8 · 生成模型:未记录

最短路径松弛累计源点距离

理解等级:中级

初始化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算法通过选择一个顶点,并不断地探寻与此顶点相关的边,以此来确定每个顶点的最短路径是否是最优