知识卡片

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

单源最短路径不只访问邻点

理解等级:中级

单对最短路径求s到指定t的最低路径代价;单源最短路径求同一s到各可达顶点的最低代价,包括通过多个中间顶点的路径。不可达点应明确表示无路径,而非赋予一个实际可走的有限代价。

单源结果可以回答多个目的地,但单对查询不一定必须先计算所有其他顶点;原文“没有其他更好的办法”不是普遍结论。允许负权时算法选择及负环对最短路径存在性的影响需要单独考虑。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      单源最短路径问题,单源最短路径问题是解决单对顶点最短路径问题过程的一部分。在单源最短路径问题中,计算从一个起始顶点s到其他与之相邻顶点之间的最短路径。之所以用这个方法解决此问题是因为没有其他更好的办法能用来解决单对顶点最短路径问题。

    参考来源

    - 位置:《算法精解:C语言描述》第16章《最短路径的描述》(spine1412;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1378.html;u296-ch16-008)。 - 结论依据:296全文单对/单源段实读;邻接点限制与必须全量求解是对原文过窄表述的边界修正。 - 原始内容:单源最短路径问题,单源最短路径问题是解决单对顶点最短路径问题过程的一部分。在单源最短路径问题中,计算从一个起始顶点s到其他与之相邻顶点之间的最短路径。之所以用这个方法解决此问题是因为没有其他更好的办法能用来解决单对顶点最短路径问题。