《6、4_2_最短路径问题_BFS算法.pdf》由会员分享，可在线阅读，更多相关《6、4_2_最短路径问题_BFS算法.pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本节内容王道考研/CSKAOYAN.COM最短路径 BFS算法王道考研/CSKAOYAN.COM最短路径问题G港R城M城Y城662P城521079“G港”是个物流集散中，经常需要往各个城市运东，怎么运送距离最近？单源最短路径问题各个城市之间也需要互相往来，相互之间怎么距离最近？每对顶点间的最短路径王道考研/CSKAOYAN.COMBFS求权图的单源最短路径12345678注：权图可以视为种特殊的带权图，只是每条边的权值都为1王道考研/CSKAOYAN.COM12345678BFS求权图的单源最短路径王道考研/CSKAOYAN.COM12345678BFS求权图的单源最短路径王道考研/CSKAO
2、YAN.COM12345678BFS求权图的单源最短路径11王道考研/CSKAOYAN.COM12345678BFS求权图的单源最短路径11王道考研/CSKAOYAN.COM12345678BFS求权图的单源最短路径11222王道考研/CSKAOYAN.COM12345678BFS求权图的单源最短路径11222王道考研/CSKAOYAN.COM12345678BFS求权图的单源最短路径1122233王道考研/CSKAOYAN.COM12345678初始都为false代码实现12345678visited falsefalsefalsefalsefalsefalsefalsefalse王道考研/
3、CSKAOYAN.COM12345678代码实现12345678visited falsefalsefalsefalsefalsefalsefalsefalse12345678d path -1-1-1-1-1-1-1-1王道考研/CSKAOYAN.COM123456782代码实现12345678visited falsetruefalsefalsefalsefalsefalsefalse12345678d 0 path -1-1-1-1-1-1-1-1王道考研/CSKAOYAN.COM123456782代码实现12345678visited falsetruefalsefalsefalsef
4、alsefalsefalse12345678d 0 path -1-1-1-1-1-1-1-1王道考研/CSKAOYAN.COM12345678216代码实现12345678visited true truefalsefalsefalsetruefalsefalse12345678d 10 1 path 2-1-1-1-12-1-1王道考研/CSKAOYAN.COM12345678216代码实现12345678visited true truefalsefalsefalsetruefalsefalse12345678d 10 1 path 2-1-1-1-12-1-1王道考研/CSKAOYAN
5、.COM12345678216代码实现12345678visited true truefalsefalsefalsetruefalsefalse12345678d 10 1 path 2-1-1-1-12-1-1王道考研/CSKAOYAN.COM123456782165代码实现12345678visited true truefalsefalsetrue truefalsefalse12345678d 10 21 path 2-1-1-112-1-1王道考研/CSKAOYAN.COM123456782165代码实现12345678visited true truefalsefalsetrue
6、 truefalsefalse12345678d 10 21 path 2-1-1-112-1-1王道考研/CSKAOYAN.COM12345678216537代码实现12345678visited true true truefalsetrue true truefalse12345678d 102212path 2-16-1126-1王道考研/CSKAOYAN.COM12345678216537代码实现12345678visited true true truefalsetrue true truefalse12345678d 102212path 2-16-1126-1王道考研/CSKA
7、OYAN.COM12345678216537代码实现12345678visited true true truefalsetrue true truefalse12345678d 102212path 2-16-1126-1王道考研/CSKAOYAN.COM12345678216537代码实现12345678visited true true truefalsetrue true truefalse12345678d 102212path 2-16-1126-1王道考研/CSKAOYAN.COM12345678216537代码实现12345678visited true true truefa
8、lsetrue true truefalse12345678d 102212path 2-16-1126-1王道考研/CSKAOYAN.COM123456782165374代码实现12345678visited true true true true true true truefalse12345678d 1023212path 2-163126-1王道考研/CSKAOYAN.COM123456782165374代码实现12345678visited true true true true true true truefalse12345678d 1023212path 2-163126-1
9、王道考研/CSKAOYAN.COM123456782165374代码实现12345678visited true true truefalsetrue true true truefalse12345678d 1023212path 2-163126-1王道考研/CSKAOYAN.COM1234567821653748代码实现12345678visited true true true true true true true true12345678d 10232123path 2-1631267王道考研/CSKAOYAN.COM1234567821653748代码实现12345678visi
10、ted true true true true true true true true12345678d 10232123path 2-1631267王道考研/CSKAOYAN.COM1234567821653748代码实现12345678visited true true true true true true true true12345678d 10232123path 2-1631267王道考研/CSKAOYAN.COM2到8的最短路径度 = d8 = 312345678d 10232123path 2-163126712345678通过path数组可知，2到8的最短路径为：8 7 6 2知识点回顾与重要考点21653748度优先成树定是以2为根的，度最的成树就是对BFS的修改，在visit个顶点时，修改其最短路径度 d 并在 path 记录前驱结点