6.4.2 最短路径

教材导航 · 第6章

原书定位

印刷页P234起,对应PDF第246页。下文为目视整理的知识提要;完整内容见原书对照。

单源问题求源点到其他顶点的距离,多源问题求任意两点距离。最短路径可不唯一;不可达距离为无穷。有负环且源点能够到达并经过它到达目标时,该对端点不存在有限最短距离。

无权图用 BFS;非负边权可用 Dijkstra;多源且没有负环时可用 Floyd。边数最少与权值和最小是不同目标。

下级知识点

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P234,PDF第246页