最短路问题D算法.ppt

最最短短路路问问题题1一、问题的提法及应用背景一、问题的提法及应用背景（1）问问题题的的提提法法寻寻求求网网络络中中两两点点间间的的最最短短路路就就是是寻寻求求连连接接这这两两个个点点的的边边的的总总权权数数最最小小的的通通路路。（注注意意：在在有有向向图图中中，通通路路开开的的初初等等链链中中所所有有的的弧弧应应是是首尾相连首尾相连的。）的。）（2）应应用用背背景景管管道道铺铺设设、线线路路安安排排、厂区布局、设备更新等。厂区布局、设备更新等。2二、最短路算法二、最短路算法1 D氏标号法（氏标号法（Dijkstra）；边权非负）；边权非负2.2.列表法（福德法）；有负权，无负回路列表法（福德法）；有负权，无负回路4v1v2v3v4v6v5v72256141341231D氏标号法（氏标号法（Dijkstra）（1 1）求解思路）求解思路从始点出发，逐步从始点出发，逐步顺序顺序地向外探寻地向外探寻，每向外延伸一步都要求是每向外延伸一步都要求是最最短的。短的。（2 2）使用条件）使用条件网络中网络中所有的弧权所有的弧权均均 非负非负，即，即 。4（3 3）选用符号的意义）选用符号的意义：P P 标号标号（Permanent固定固定/永久性标号）永久性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权 T T 标号标号（Temporary临时性标号）临时性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权上界上界5（4 4）计算步骤及例子：计算步骤及例子：第第一一步步：给给起起始始点点v1标标上上固固定定标标号号,其其余各点标临时性标号余各点标临时性标号T(vj)=,j 1;=l1j第二步第二步：考虑满足如下条件的所有点：考虑满足如下条件的所有点与与v1相邻的点，即相邻的点，即;具有具有T 标号，即标号，即，为为T 标号点集标号点集.修修改改的的T标标号号为为，并并将将结结果仍记为果仍记为T(vj)。svjv若网络图中已无满足此条件的若网络图中已无满足此条件的T标号点，停止计算。标号点，停止计算。6第第三三步步：令令,然然后后将将的的T 标标号号改改成成P 标标号号，转转入入第第二二步步。此此时时，要要注意将第二步中的注意将第二步中的改为改为。7例一、例一、用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。v1v2v3v4v6v5352242421 解解 （1）首先给v1以P标号，给其余所有点T标号。（2）8例一、例一、用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。v1v2v3v4v6v5352242421（4）9v1v2v3v4v6v5352242421（5）（6）反向追踪得v1到v6的最短路为：10237184566134105275934682求从求从1到到8的最短路径的最短路径11237184566134105275934682X=1min d12,d14,d16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1p4=1p1=012237184566134105275934682X=1,4min d12,d16,d42,d47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,p2=2p1=0p4=1p2=213237184566134105275934682X=1,2,4min d16,d23,d25,d47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,p6=3p2=2p4=1p1=0p6=314237184566134105275934682X=1,2,4,6min 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=3p2=2p4=1p1=0p6=3p7=315237184566134105275934682X=1,2,4,6,7min 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=6p2=2p4=1p1=0p6=3p7=3p5=616237184566134105275934682X=1,24,6,7min 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=8p2=2p4=1p1=0p6=3p7=3p5=6p3=817237184566134105275934682X=1,2,3,4,6,7min d38,d58,d78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=1018237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=1019此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！20