1、 最最 短短 路路 问问 题题*寻求网络中两点间寻求网络中两点间的最短路就是寻求连接这两个点的边的的最短路就是寻求连接这两个点的边的总权数最小的总权数最小的通路通路。（注意：在有向图。（注意：在有向图中，通路中，通路中所有的弧应中所有的弧应是是的。）的。）管道铺设、线路安排、管道铺设、线路安排、厂区布局、设备更新等。厂区布局、设备更新等。*4v1v2v3v4v6v5v722561413412*从始点出发，逐步从始点出发，逐步顺序顺序地向外探寻地向外探寻，每向外延伸一步都要求是每向外延伸一步都要求是网络中网络中所有的弧权所有的弧权均均 ，即，即 。*：P P 标号标号（Permanent固定固定
2、/永久性标号）永久性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权 T T 标号标号（Temporary临时性标号）临时性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权*0)(1vp 第一步第一步：给起始点：给起始点v1标上固定标号标上固定标号 ,其余各点标临时性标号其余各点标临时性标号 T(vj)=,j 1;=l1jjv s jv 第二步第二步：考虑满足如下条件的所有点：考虑满足如下条件的所有点 与与 v1相邻的点，即相邻的点，即 ;具有具有T 标号，即标号，即 ，为为T 标号点集标号点集.修改修改 的的T标号为标号为 ，并将结，并将结果仍记为果仍记为T(vj)。sv
3、jjv)(),(min11jjlvpvTv若网络图中已无满足此条件的若网络图中已无满足此条件的T标号点，停止计算。标号点，停止计算。*第三步第三步：令令 ,然后然后将将 的的T 标号改成标号改成P 标号标号，转入第二步。此时，转入第二步。此时，要要注意将第二步中的注意将第二步中的 改为改为 。1v 0jv 0jv)(min)(0jsvjvTvTj*例一、例一、用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。v1v2v3v4v6v5352242421 解解 （1）首先给v1以P标号，给其余所有点T标号。0)(1vP)6,3,2()(ivTi（2）330,min)(,)
4、(min)(12122lvPvTvT550,min)(,)(min)(13133lvPvTvT3)(,3)()(),(),(),(),(min)(min2265432vpvTvTvTvTvTvTvTjsvj所以有，*例一、例一、用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。v1v2v3v4v6v5352242421（4）4 13,5min)(,)(min)(23233lvPvTvT523,min)(,)(min)(24244lvPvTvT523,min)(,)(min)(25255lvPvTvT4)(,4)()(),(),(),(min)(min336543vpv
5、TvTvTvTvTvTjsvj所以有，*v1v2v3v4v6v5352242421（5）544,5min)(,)(min)(35355lvPvTvT725,45,min)(,)(,)(min)(56546466lvPlvPvTvT（6）反向追踪得v1到v6的最短路为：6521vvvv5)(,5)(,5)()()(),(),(min)(min5454654vpvpvTvTvTvTvTvTjsvj所以有，7)(,7)(min)(min66vpvTvTjsvj所以有，*237184566134105275934682求从求从1到到8的最短路径的最短路径*23718456613410527593468
6、2X=1min d12,d14,d16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1p4=1p1=0*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*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*2371845661
7、34105275934682X=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=3*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*237184566134105275934682X=1,2,4,6,7min d23,d53,d58,d78=
8、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=8*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*237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10*
