知识卡片

普通读书笔记卡 · 5654.d.1.f.4.h · 生成模型:未记录

最短路加法须检查无穷与溢出

理解等级:中级

计算候选距离前先判断起点距离是否为无穷,并检查有限距离加边权是否超出可表示范围;用更宽类型只有在确认其范围足够时才安全。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前仍需验证是否可表示;无穷哨兵也不能直接作为正常距离参与计算。 - 原始内容:长整型。