最短路问题Dijkstra算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,10.3 最短路问题,最短路问题是网络理论中应用最广泛的问题之一.,许多优化问题可以使用这个模型如设备更新、管道铺设、线路安排、厂区布局等.,我们曾介绍了最短路问题的动态规划解法，但某些最短路问题(如道路不能整齐分段者)构造动态规划方程比较困准、而图论方法则比较有效。,最短路问题：在一个赋权图G上，给定两个顶点,u,和,v,，在所有连接顶点,u,和,v,的路中，寻找路长最短的路（称为,u,和,v,最短路.,）,u,和,v,最短路的路长也称为,u,和,v,的,距离-,d,(,u,v,).,有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、或求网络中任意两点间的最短路.,1,一、网络无负权的最短路,本算法由,Dijkstra,于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。,算法的基本思路基于以下,原理,：,若序列,v,s,v,1,v,n,是从,v,s,到,v,n,的最短路，,则序列,v,s,v,1,v,n-,1,必为从,v,s,到,v,n-,1,的最短路。,Dijkstra,算法,2,Dijkstra,算法,基本思想,Dijkstra,算法的基本思想是从,v,s,出发，逐步地向外探寻最短路，采用,标号法,。,执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从,v,s,到该点的最短路长（称为,P,标号,），或者是从,v,s,到该点的最短路长的上界（称为,T,标号,）。,算法每一步都把某个顶点的,T,标号改为,P,标号， 当终点,v,t,得到,P,标号时，计算结束。最多,n,-1步。,3,计算实例：,求连接,v,s,、,v,t,的最短路.,0,-,-,-,P,T,-,-,-,-,开始，给,v,s,以,P,标号，,P,(,v,s,)=0,其余各点给,T,标号,T,(,v,i,)=+.,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,Step 1:,迭代 1,Dijkstra,算法,基本步骤：,4,0,-,-,-,-,-,-,-,若,v,i,为刚得到,P,标号的点,考虑这样的点,v,j,: (,v,i,v,j,),E 且,v,j,为,T,标号。,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,Step 2:,对,v,j,的,T,标号进行如下更改,T,(,v,j,)=,min,T,(,v,j,),P,(,v,i,)+,w,ij,2,4,5,迭代 1,考察,v,s,T,(,v,2,)=,min,T,(,v,2,),P,(,v,s,)+,w,s,2,=,min,+,0+5=5,T,(,v,1,)=,min,T,(,v,1,),P,(,v,s,)+,w,s,1,=,min,+,0+2=2,5,0,-,-,-,-,-,-,-,比较所有具有,T,标号的点，把最小者改为,P,标号，,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,Step 3:,2,4,5,即,P,(,v,i,)=,min,T,(,v,i,).,当存在两个以上最小者时,可同时改为,P,标号。若全部点为P标号,则停止。否则用,v,i,代替,v,i,转step 2.,-,2,迭代 1,全部,T,标号中,T,(,v,1,)最小,令,P,(,v,1,)=2,记录路径(,v,s,v,1,).,6,0,-,2,-,-,5,-,-,-,-,4,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,9,4,若,v,i,为刚得到,P,标号的点,考虑这样的点,v,j,: (,v,i,v,j,),E 且,v,j,为,T,标号。,Step 2:,对,v,j,的,T,标号进行如下更改,T,(,v,j,)=,min,T,(,v,j,),P,(,v,i,)+,w,ij,迭代 2,考察,v,1,T,(,v,4,)=,min,T,(,v,4,),P,(,v,1,)+,w,14,=,min,+,2+7=9,T,(,v,2,)=,min,T,(,v,2,),P,(,v,1,)+,w,12,=,min,5,2+2=4,7,0,-,2,-,-,4,-,9,-,-,-,4,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,4,4,迭代 2,比较所有具有,T,标号的点，把最小者改为,P,标号，,Step 3:,即,P,(,v,i,)=,min,T,(,v,i,).,-,-,全部,T,标号中,T,(,v,2,),T,(,v,3,)最小,令,P,(,v,2,)=4,P,(,v,3,)=4,记录路径(,v,1,v,2,), (,v,1,v,4,),.,8,0,-,2,-,4,-,-,9,-,-,4,-,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,7,迭代 3,若,v,i,为刚得到,P,标号的点,考虑这样的点,v,j,: (,v,i,v,j,),E 且,v,j,为,T,标号。,Step 2:,对,v,j,的,T,标号进行如下更改,T,(,v,j,)=,min,T,(,v,j,),P,(,v,i,)+,w,ij,9,0,-,2,-,4,-,-,9,-,-,7,4,-,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,7,迭代 3,比较所有具有,T,标号的点，把最小者改为,P,标号，,Step 3:,即,P,(,v,i,)=,min,T,(,v,i,).,-,10,0,-,2,-,4,-,-,9,-,7,-,4,-,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,迭代 4,若,v,i,为刚得到,P,标号的点,考虑这样的点,v,j,: (,v,i,v,j,),E 且,v,j,为,T,标号。,Step 2:,对,v,j,的,T,标号进行如下更改,T,(,v,j,)=,min,T,(,v,j,),P,(,v,i,)+,w,ij,8,14,11,0,-,2,-,4,-,-,8,-,14,7,-,4,-,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,迭代 4,8,-,比较所有具有,T,标号的点，把最小者改为,P,标号，,Step 3:,即,P,(,v,i,)=,min,T,(,v,i,).,12,0,-,2,-,4,-,8,-,-,14,7,-,4,-,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,迭代 5,13,若,v,i,为刚得到,P,标号的点,考虑这样的点,v,j,: (,v,i,v,j,),E 且,v,j,为,T,标号。,Step 2:,对,v,j,的,T,标号进行如下更改,T,(,v,j,)=,min,T,(,v,j,),P,(,v,i,)+,w,ij,13,0,-,2,-,4,-,8,-,-,13,7,-,4,-,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,迭代 5,13,比较所有具有,T,标号的点，把最小者改为,P,标号，,Step 3:,即,P,(,v,i,)=,min,T,(,v,i,).,当存在两个以上最小者时,可同时改为,P,标号。若全部点为P标号,则停止。否则用,v,i,代替,v,i,转step 2.,-,14,0,-,2,-,4,-,8,-,13,-,7,-,4,-,2,2,7,4,1,4,7,3,1,5,5,5,v,s,v,2,v,1,v,t,v,4,v,5,v,3,最短路,Dijkstra,算法不仅找到了所求最短路，而且找到了从,v,s,点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。,15,开始，给,v,s,以,P,标号，,P,(,v,s,)=0,其余各点给,T,标号,T,(,v,i,)=+.,Step 1:,若,v,i,为刚得到,P,标号的点,考虑这样的点,v,j,: (,v,i,v,j,),E 且,v,j,为,T,标号。,Step 2:,对,v,j,的,T,标号进行如下更改,T,(,v,j,)=,min,T,(,v,j,),P,(,v,i,)+,w,ij,比较所有具有,T,标号的点，把最小者改为,P,标号，,Step 3:,即,P,(,v,i,)=,min,T,(,v,i,).,当存在两个以上最小者时,可同时改为,P,标号。若全部点为P标号,则停止。否则用,v,i,代替,v,i,转step 2.,Dijkstra,算法,步骤：,16,(2) 考察,v,s,T,(,v,2,)=,min,T,(,v,2,),P,(,v,s,)+,w,s,2,=,min,+,0+5=5,T,(,v,1,)=,min,T,(,v,1,),P,(,v,s,)+,w,s,1,=,min,+,0+2=2,(3) 全部,T,标号中,T,(,v,1,)最小,令,P,(,v,1,)=2,记录路径(,v,s,v,1,).,(4)考察,v,1,T,(,v,4,)=,min,T,(,v,4,),P,(,v,1,)+,w,14,=,min,+,2+7=9,T,(,v,2,)=,min,T,(,v,2,),P,(,v,1,)+,w,12,=,min,5,2+2=4,(5) 全部,T,标号中,T,(,v,2,),T,(,v,3,)最小,令,P,(,v,2,)=4,P,(,v,3,)=4,记录路径(,v,1,v,2,), (,v,1,v,4,),.,T,(,v,3,)=,min,T,(,v,3,),P,(,v,s,)+,w,s,3,=,min,+,0+4=4,解:,(1)首先，给,v,s,以,P,标号，,P,(,v,s,)=0,其余各点给,T,标号,T,(,v,i,)=+.,.,17,