最短路问题-迪杰斯特拉算法.ppt

最 短 路 问 题,一、问题的提法及应用背景,（1）问题的提法寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数最小的通路。（注意：在有向图中，通路开的初等链中所有的弧应是首尾相连的。）（2）应用背景管道铺设、线路安排、厂区布局、设备更新等。,二、最短路算法,1 D氏标号法（Dijkstra）；边权非负2.列表法（福德法）；有负权，无负回路,1D氏标号法（Dijkstra）（1）求解思路从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。,（2）使用条件网络中所有的弧权均 非负，即。,（3）选用符号的意义：P 标号（Permanent固定/永久性标号）从始点到该标号点的最短路权 T 标号（Temporary临时性标号）从始点到该标号点的最短路权上界,（4）计算步骤及例子：,第一步：给起始点v1标上固定标号,其余各点标临时性标号 T(vj)=,j1;,=l1j,若网络图中已无满足此条件的T标号点，停止计算。,第三步：令,然后将 的T 标号改成P 标号，转入第二步。此时，要注意将第二步中的 改为。,例一、用Dijkstra算法求下图从v1到v6的最短路。,解（1）首先给v1以P标号，给其余所有点T标号。,（2）,例一、用Dijkstra算法求下图从v1到v6的最短路。,（4）,（5）,（6）,反向追踪得v1到v6的最短路为：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,min d12,d14,d16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min d12,d16,d42,d47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,p2=2,p1=0,p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min d16,d23,d25,d47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,p6=3,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min d23,d25,c47,d67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min d23,d25,d75,d78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min d23,d53,d58,d78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7,p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min d38,d58,d78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,