知识卡片
最短路加法须检查无穷与溢出
计算候选距离前先判断起点距离是否为无穷,并检查有限距离加边权是否超出可表示范围;用更宽类型只有在确认其范围足够时才安全。C++有符号溢出不能靠事后检查 newLen≥0可靠检测,且负权本身也使这种检查无效。
Dijkstra标准正确性要求边权非负,包含零;负权会使结果不可靠,是否死循环取决于实现,不应一概而论。
162示例以long计算newLen,但long宽度依平台而定,结果写回int前仍需验证是否可表示;无穷哨兵也不能直接作为正常距离参与计算。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 最短路加法须检查无穷与溢出
- · 结论
原书出处 · 2 处
参考来源
- 位置:《算法技术手册》第6章《输入/输出》(spine1574;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1537.html;u160-ch06-009)。
- 结论依据:160全文、03291伪代码及03293–03294实现对照实读。
- 原始内容:算术溢出,你必须注意,简单地添加一个对newLen≥0的检查。 图 6-13 使用优先队列的Dijkstra算法详解
- 位置:《算法技术手册》第6章《结论》(spine1576;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1539.html;u162-ch06-009)。
- 结论依据:162示例以long计算newLen,但long宽度依平台而定,结果写回int前仍需验证是否可表示;无穷哨兵也不能直接作为正常距离参与计算。
- 原始内容:长整型。