6.3.1.1 BFS 求无权图最短路径
原书定位
印刷页P221起,对应PDF第233页。下文为目视整理的知识提要;完整内容见原书对照。
令起点距离为 0,其余为无穷。首次从 发现 时令 ,并记录前驱,得到从源点到可达顶点的最少边数及一条相应路径。
适用于无权图,或每条边具有相同正权的图。一般带权图按边数分层不保证权值和最小;需选择适用的带权最短路径算法。
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P221起,对应PDF第233页。下文为目视整理的知识提要;完整内容见原书对照。
令起点距离为 0,其余为无穷。首次从 发现 时令 ,并记录前驱,得到从源点到可达顶点的最少边数及一条相应路径。
适用于无权图,或每条边具有相同正权的图。一般带权图按边数分层不保证权值和最小;需选择适用的带权最短路径算法。
