知识卡片
最短路径查询方向决定图变换
最短路径问题可按查询端点区分:固定起点求到各点、固定终点求各点到它、指定一对端点,以及所有点对。无向图中交换起终点不改变路径长度;有向图若要用单源算法回答“到同一终点”的查询,可先反转所有边再从该终点出发。建模前确认方向和边权,否则把不同查询当成同一问题,可能得到反向可达性或错误距离。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 8 . 1 最 短 路 径 搜 索 · 查看原书依据
(2)已知终结节点,求最短路径。该问题与确定起点的问题在无向图的最短路径搜索中完全等同,而在有向图中该问题等同于把所有路径方向反转的确定起点问题。 (3)确定起点终点的最短路径问题,即求两点之间的最短路径。
参考来源
- 位置:《智能算法导论》第 174 项《1 8 . 1 最 短 路 径 搜 索》(源文件:`_epub-src/EPUB/xhtml/chapter18_0002.xhtml`)
- 结论依据:正文列出固定起点、固定终点、指定起终点和全局最短路径四种形式,并说明有向图固定终点可通过反转所有路径方向转换为固定起点问题。
- 原始内容:已知起始节点,求最短路径。已知终结节点,求最短路径。该问题与确定起点的问题在无向图的最短路径搜索中完全等同,而在有向图中该问题等同于把所有路径方向反转的确定起点问题。