知识卡片
不可达点不能复用上轮选点
shortest每轮用DBL_MAX初始化minimum,仅在白色顶点d严格更小时更新adjlist;若剩余顶点不可达,无新候选时仍使用上轮adjlist,可能重复处理旧顶点并在循环结束后返回0,仅收集黑色点。它没有明确报告不可达,也没有保证所有顶点变黑。
relax实际以v.d>u.d+weight严格更新,不是正文所说的小于或等于;它没有验证边权非负,也不检查目标颜色。负权、浮点溢出或NaN等输入不能据返回0推定结果正确。找不到start之前已初始化图状态,且paths尚未初始化;结果列表插入失败则销毁已初始化列表,但不回滚图状态。以上是静态阅读推导,没有运行C程序。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
DBL_MAX(除了起始顶点外,起始顶点初始估计值为0.0)。用存储在邻接表结构链表中的顶点来维护顶点的色值、最短路径估计和父结点。其原因与计算最小生成树时的解释相同。 Dijkstra算法的核心是用一个单循环为图中的每个结点迭代一次。在每次迭代过程中,首先在所有白色顶点中选择最短路径估计最小的顶点
参考来源
- 位置:《算法精解:C语言描述》第16章《最短路径的实现与分析》(spine1414;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1380.html;u299-ch16-010)。
- 结论依据:299全文和03086–03088完整源码实读,逐项对照候选选择、relax、失败路径及结果收集。
- 原始内容:DBL_MAX(除了起始顶点外,起始顶点初始估计值为0.0)。用存储在邻接表结构链表中的顶点来维护顶点的色值、最短路径估计和父结点。其原因与计算最小生成树时的解释相同。 Dijkstra算法的核心是用一个单循环为图中的每个结点迭代一次。在每次迭代过程中,首先在所有白色顶点中选择最短路径估计最小的顶点