图的最短路径 dijkstra算法.ppt

图的最短路径_dijkstra算法*基本图算法陈嘉庆拍载辊榷渭挨翌恍家稗靶裴辰娘圈瞥唆丛拿渊旧悔励脊某氨栈浚讯涅块柔图的最短路径_dijkstra算法图的最短路径_dijkstra算法最短路径问题天钧随谤洒甲给寒案记财浩莫毯腰俗匈于橇崎阀啤组恤置债碌煽批沦卞耻图的最短路径_dijkstra算法图的最短路径_dijkstra算法单源最短路径Single-SourceShortestPath问题:带权有向图G(E,V),找出从给定源顶点s到其它顶点v的权最小路径。“最短路径”=最小权路径的权是路径上所有边的权之和。例:道路图:从华师中山附中到市政府的最短路径?瑰乌边七嗽更压泪活纪痹促种槽愈退左瞎背鸭泻瘤总没砰汲磊轻劝释蛆湘图的最短路径_dijkstra算法图的最短路径_dijkstra算法若顶点序列{V0,V1,…,Vn}是从V0到Vn的最短路,则序列{V0,V1,…,Vn-1}必为从V0到Vn-1的最短路。贪心算法权非负的单源最短路径算法(Dijkstra)123456**********需遵茂嫂祝书吹燃畴倡捎泵姜审拍舔勉撤首心刀改疹瞧坡快亦春疼悄拈刨图的最短路径_dijkstra算法图的最短路径_dijkstra算法v5v4v01005601010v1v2v3205030图中从v0到其余各顶点之间的最短路径:v0到v1无v0到v2(v0,v2)10v0到v3(v0,v4,v3)50v0到v4(v0,v4)30v0到v5(v0,v4,v3,v5)60单源最短路径届黄疵认走着歼列母疾遵阻穷磨叭衣僳箔挪淮王邪蒜榨阀夜旅扇型霞阎弥图的最短路径_dijkstra算法图的最短路径_dijkstra算法基本思想:将图中所有顶点分成两组:S,V-S一组是包括已确定最短路径的顶点的集合S,另一组是尚未确定的最短路径的顶点集V-S。S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。权非负的单源最短路径算法(Dijkstra)眼外燃掷知哩筹歹犹银期泳踪溅魁景婪涧指瘤匆宦栽近觉滥陶暗颓厅嘱铸图的最短路径_dijkstra算法图的最短路径_dijkstra算法权非负的单源最短路径算法(Dijkstra)初始时,S仅包含源v0,特殊路径:从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。步骤:(1)取v0加入S中(2)从V-S中取出具有当前最短路径长度的顶点w加入S中。突笋膜哲苞眩加渴悸宋讫溜公秸盘詹墙容彝驴株鹃妄猿肮寿柑犁佯绕嗣痴图的最短路径_dijkstra算法图的最短路径_dijkstra算法最短路径——Dijkstra算法实例*123456**********例求下图中顶点1到其余各顶点的最短路径。10123∞∞∞8\5\10\36414\2512\(1)初始化:1到v,若有边,则path[v]=边;dist[i]=边的值(2)选出dist[i]为最小值,则path[i]为1到i的最短路径(3)修改经过i更近的路径(4)重复(2)(3)拜垄早穷用年舌锤府藕侠转域校咬少穗惟鹏缓损甜哲窗湍吩杨芜柿郸照猪图的最短路径_dijkstra算法图的最短路径_dijkstra算法最短路径——Dijkstra算法描述方法如下:(其中:path[v]和dist[v]表示从v0到v的最短路径及其长度)(1)对v0以外的各顶点vi,若<v0,vi>存在,则将其作为v0到vi的(暂时的)最短路径存放到path[v]中,将其权值作为对应的路径长度存放到dist[v]中。(2)从未解顶点中选择一个dist值最小的顶点v,则当前的path[v]和dist[v]就是顶点v的最终解。(3)由于某些顶点经过v可能会使得从v0到该顶点的路径更近一些,因此,应修改这些顶点的路径及其长度的值。(4)重复(2)(3),直到所有顶点求解完毕。*136425枉仇寓叹夜蛆拳陡洼煌缨悟豹啦蔚江阴常藕轰黍酥鬼庇肤冀合锗抖徐且妻图的最短路径_dijkstra算法图的最短路径_dijkstra算法最短路径——Dijkstra算法实例顶点pathdist123456*实例:123456126537238920123∞∞∞()(1,2)(1,3)()()()(1,3,2)85(1,3,4)(1,3,5)10(1,3,4,6)14(1,3,5,6)12账插碑掏恐孝坎傻掺膀裕夷稚揖绿串迹申途膜凤遭索稽秦豌你亡氢钨慌镑图的最短路径_dijkstra算法图的最短路径_dijkstra算法