《最短路问题迪杰斯特拉算法.pptx》由会员分享，可在线阅读，更多相关《最短路问题迪杰斯特拉算法.pptx（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、问题的提法及应用背景（1）问题的提法寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数最小的通通路路。（注意：在有向图中，通路开的初等链中所有的弧应是首尾相连的。）（2）应用背景管道铺设、线路安排、厂区布局、设备更新等。第1页/共19页二、最短路算法二、最短路算法1 1 DD氏标号法（氏标号法（氏标号法（氏标号法（DijkstraDijkstra）；边权非负）；边权非负）；边权非负）；边权非负2.2.2.2.列表法（福德法）；有负权，无负回路列表法（福德法）；有负权，无负回路列表法（福德法）；有负权，无负回路列表法（福德法）；有负权，无负回路4v1v2v3v4v6v5v7225614
2、13412第2页/共19页1D氏标号法（氏标号法（Dijkstra）（1 1 1 1）求解思路）求解思路）求解思路）求解思路从始点出发，逐步从始点出发，逐步顺序地向外探寻顺序地向外探寻，每向外延伸一步都要求每向外延伸一步都要求是是最短的。最短的。最短的。最短的。（2 2）使用条件）使用条件网络中网络中所有的弧权所有的弧权均均 非负非负，即，即 。第3页/共19页（3 3）选用符号的意义）选用符号的意义：P P 标号标号（Permanent固定固定/永久性标号）永久性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权 T T 标号标号（Temporary临时性标号）临时性标号）从始点到该
3、标号点的最短路权从始点到该标号点的最短路权上界上界第4页/共19页（4 4）计算步骤及例子：计算步骤及例子：第一步：给起始点v1标上固定标号 ,其余各点标临时性标号 T(vj)=,j 1;=l1j第二步：考虑满足如下条件的所有点 与 v1相邻的点，即 ;具有T 标号，即 ，为T 标号点集.修改 的T标号为 ，并将结果仍记为T(vj)。svj若网络图中已无满足此条件的T标号点，停止计算。第5页/共19页第三步：令 ,然后将 的T 标号改成P 标号，转入第二步。此时，要注意将第二步中的 改为 。第6页/共19页例一、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v53522
4、42421 解 （1）首先给v1以P标号，给其余所有点T标号。（2）第7页/共19页例一、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421（4）第8页/共19页v1v2v3v4v6v5352242421（5）（6）反向追踪得v1到v6的最短路为：第9页/共19页237184566134105275934682求从求从1到到8的最短路径的最短路径第10页/共19页237184566134105275934682X=1min d12,d14,d16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1p4=1p1=0第11页/共19
5、页237184566134105275934682X=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=2第12页/共19页237184566134105275934682X=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=3第13页/共19页237184566134105275934682X=1,2,4,6min d23,d25,c47,d67=min 2+
6、6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,p7=3p2=2p4=1p1=0p6=3p7=3第14页/共19页237184566134105275934682X=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=6第15页/共19页237184566134105275934682X=1,2,4,6,7min d23,d53,d58,d78=min 2+6,6+9,6+4,3+8=min 8,15,10,1
7、1=8X=1,2,3,4,5,6,7,p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8第16页/共19页237184566134105275934682X=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=10第17页/共19页237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10第18页/共19页感谢您的观看！第19页/共19页