最短路问题--D算法

最短路问题一、问题的提法及应用背景（1）问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数最小的通路。（注意：在有向图中，通路——开的初等链中所有的弧应是首尾相连的。）（2）应用背景——管道铺设、线路安排、厂区布局、设备更新等。二、最短路算法1．D氏标号法（Dijkstra）；边权非负2.列表法（福德法）；有负权，无负回路4v1v2v3v4v6v5v7225614134121．D氏标号法（Dijkstra）（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。（2）使用条件——网络中所有的弧权均非负，即。0ijl（3）选用符号的意义：①P标号（Permanent固定/永久性标号）——从始点到该标号点的最短路权②T标号（Temporary临时性标号）——从始点到该标号点的最短路权上界（4）计算步骤及例子：0)(1vp第一步：给起始点v1标上固定标号,其余各点标临时性标号T(vj)=,j1;=l1jjvsjvAvvj),(1第二步：考虑满足如下条件的所有点①与v1相邻的点，即;②具有T标号，即，为T标号点集.修改的T标号为，并将结果仍记为T(vj)。svjjv})(),(min{11jjlvpvT若网络图中已无满足此条件的T标号点，停止计算。第三步：令,然后将的T标号改成P标号，转入第二步。此时，要注意将第二步中的改为。1v0jv0jv)}({min)(0jsvjvTvTj例一、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421解（1）首先给v1以P标号，给其余所有点T标号。0)(1vP)6,,3,2()(ivTi（2）3]30,min[])(,)(min[)(12122lvPvTvT5]50,min[])(,)(min[)(13133lvPvTvT3)(,3)()}(),(),(),(),(min{)}({min2265432vpvTvTvTvTvTvTvTjsvj所以有，例一、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421（4）4]13,5min[])(,)(min[)(23233lvPvTvT5]23,min[])(,)(min[)(24244lvPvTvT5]23,min[])(,)(min[)(25255lvPvTvT4)(,4)()}(),(),(),(min{)}({min336543vpvTvTvTvTvTvTjsvj所以有，v1v2v3v4v6v5352242421（5）5]44,5min[])(,)(min[)(35355lvPvTvT7]25,45,min[])(,)(,)(min[)(56546466lvPlvPvTvT（6）反向追踪得v1到v6的最短路为：6521vvvv5)(,5)(,5)()()}(),(),(min{)}({min5454654vpvpvTvTvTvTvTvTjsvj所以有，7)(,7)}(min{)}({min66vpvTvTjsvj所以有，237184566134105275934682求从1到8的最短路径237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={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=2p1=0p4=1p2=2237184566134105275934682X={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=3p2=2p4=1p1=0p6=3237184566134105275934682X={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=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={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=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={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=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={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=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10