6.4.2 最短路径
原书定位
印刷页P234起,对应PDF第246页。下文为目视整理的知识提要;完整内容见原书对照。
单源问题求源点到其他顶点的距离,多源问题求任意两点距离。最短路径可不唯一;不可达距离为无穷。有负环且源点能够到达并经过它到达目标时,该对端点不存在有限最短距离。
无权图用 BFS;非负边权可用 Dijkstra;多源且没有负环时可用 Floyd。边数最少与权值和最小是不同目标。
下级知识点
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P234起,对应PDF第246页。下文为目视整理的知识提要;完整内容见原书对照。
单源问题求源点到其他顶点的距离,多源问题求任意两点距离。最短路径可不唯一;不可达距离为无穷。有负环且源点能够到达并经过它到达目标时,该对端点不存在有限最短距离。
无权图用 BFS;非负边权可用 Dijkstra;多源且没有负环时可用 Floyd。边数最少与权值和最小是不同目标。
