2最短路径问题Dijkstra算法

本节内容最短路径Dijkstra算法研/CSKAOYAN迪杰斯特拉•

提出“goto有害理论”——操作系统，虚拟存储技术

•

信号量机制PV原语——操作系统，进程同步

•

银⾏家算法——操作系统，死锁

•

解决哲学家进餐问题——操作系统，死锁

•

Dijkstra最短路径算法——数据结构⼤题、⼩题艾兹格·W·迪杰斯特拉

EdsgerWybeDijkstra(1930~2002)1972年图灵奖得主研/CSKAOYANBFS算法的局限性R城6Y城10G港52967P城2M城研/CSKAOYANBFS算法的局限性R城6Y城G港10296带权路径⻓度——当图是带权图时，⼀条路径上所有边的权值之和，称为该路径的带权路径⻓度57BFS算法求单源最短路径只适⽤于⽆P城2M城权图，或所有边的权值都相同的图研/CSKAOYANDijkstra算法V11V2R城6Y城V01023946G港102965757V42V3P城2M城研/CSKAOYANDijkstra算法10V11V210R城6Y城V0523946G港529677V42V3P城2M城研/CSKAOYANDijkstra算法初始：从V0开始，初始化三个数组信息如下👇V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌❌径⻓度5V427V3路径上dist[5]的前驱path[5]-10-1-10010∞∞5研/CSKAOYANDijkstra算法第1轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌❌径⻓度5V427V3路径上dist[5]的前驱path[5]-10-1-10010∞∞5研/CSKAOYANDijkstra算法第1轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌❌径⻓度5V427V3路径上dist[5]的前驱path[5]-10-1-10010∞∞5研/CSKAOYANDijkstra算法第1轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌✔径⻓度5V427V3路径上dist[5]的前驱path[5]-10-1-10010∞∞5研/CSKAOYANDijkstra算法第1轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌✔径⻓度5V427V3路径上dist[5]的前驱path[5]-10-1-10010∞∞5检查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYANDijkstra算法第1轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌✔径⻓度5V427V3路径上dist[5]的前驱path[5]-10-1-10010∞∞5检查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYANDijkstra算法第1轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌✔径⻓度5V427V3路径上dist[5]的前驱path[5]查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYANDijkstra算法第2轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌✔径⻓度5V427V3路径上dist[5]的前驱path[5]/CSKAOYANDijkstra算法第2轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌❌✔径⻓度5V427V3路径上dist[5]的前驱path[5]/CSKAOYANDijkstra算法第2轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]/CSKAOYANDijkstra算法第2轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYANDijkstra算法第2轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYANDijkstra算法第3轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]/CSKAOYANDijkstra算法第3轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔❌❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]/CSKAOYANDijkstra算法第3轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔✔❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]/CSKAOYANDijkstra算法第3轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔✔❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYANDijkstra算法第3轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔✔❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYANDijkstra算法第3轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔✔❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]-1414008975检查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYANDijkstra算法第4轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔✔❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]-1414008975研/CSKAOYANDijkstra算法第4轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔✔❌✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]-1414008975研/CSKAOYANDijkstra算法第4轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔✔✔✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]-1414008975研/CSKAOYANDijkstra算法第4轮：循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]V0V1V2V3V4✔✔✔✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]-1414008975检查所有邻接⾃Vi

的顶点，若其final值为false，则更新dist和path信息研/CSKAOYAN如何使⽤数组信息？V11V2标记各顶点是否V01023946已找到最短路径最短路final[5]V0V1V2V3V4✔✔✔✔✔径⻓度5V427V3路径上dist[5]的前驱path[5]-1414008975V0到V2的最短(带权)路径⻓度为：dist[2]=9通过path[]可知，V0到V2的最短(带权)路径：V2<——V1<——V4<——V0研/CSKAOYANDijkstra算法的时间复杂度V0102V13194V26标记各顶点是否已找到最短路径最短路final[5]径⻓度V0V1V2V3V4✔❌❌❌❌5V427V3路径上dist[5]的前驱path[5]初始：若从V0开始，令final[0]=ture;dist[0]=0;path[0]=-1。时间复杂度：其余顶点final[k]=false;dist[k]=arcs[0][k];path[k]=(arcs[0][k]==∞)?-1:0O(n2)即O(|V|2)-10-1-10010∞∞5n-1轮处理：循环遍历所有顶点，找到还没确定最短路径，且dist最⼩的顶点Vi，令final[i]=ture。并检查所有邻接⾃Vi的顶点，对于邻接⾃Vi的顶点Vj，若final[j]==false且dist[i]+arcs[i][j]<dist[j]，则令dist[j]=dist[i]+a