Python实现Dijkstra最短路径算法出现浮点精度异常问题求助

你遇到的异常值不是Dijkstra算法逻辑出错导致的，是二进制浮点数精度固有缺陷带来的正常现象：绝大多数十进制的一位小数（比如0.1、0.2）无法用二进制浮点数精确表示，多次累加计算后微小的误差会累积，就会出现22.400000000000002这类和预期值只差极小精度误差的结果，实际数值和你期望的22.4几乎没有差异，只是显示不符合预期。

你可以根据使用场景选择以下任意一种方案解决：

• 方案一：输出时做精度截断
  因为你所有输入的边权都是一位小数，最终结果只要保留一位小数就能得到正确值，只需要在输出时对结果做四舍五入处理即可，改动最小：

  res = dijkstra(graph, index[5])
  # 对所有距离值保留一位小数
  formatted_res = {node: round(dist, 1) for node, dist in res.items()}
  print('from', index[5], 'to', formatted_res)
  

• 方案二：转为整数运算彻底避免精度问题
  把所有边权统一乘以10转为整数存储和计算，整数运算完全没有精度误差，最终结果再除以10还原即可，适合需要完全消除浮点误差的场景：
  例如修改graph定义时，把5.3改为53、4.7改为47，以此类推，最终返回距离时每个值除以10就得到正确的一位小数结果。
• 方案三：使用decimal模块做精确十进制运算
  如果后续需要扩展更高精度的小数，可以使用Python标准库的decimal模块实现精确的十进制浮点运算，不需要改动算法逻辑，只需要替换数值类型即可。

你的Dijkstra算法实现本身没有逻辑问题，不需要修改算法核心代码。

内容的提问来源于stack exchange，提问作者Jiyoun