第十一章 最短路问题

第十一章,最短路问题,一、引例,例1：已知如图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需的费用。现在某人要从v1出发通过这个交通网到v8，求使总费用最小的旅行路线。,对于有向图G或无向图G的每一条边e，附加一个实数w(e),则称w(e)为边e上的权，当e=(vi,vj)时，w(e)也可记为wij。G连同其各边上的权称为带权图，带权图常记为G=。,上式中对G中所有从vs到vt的路P取最小，称P0为从vs到vt的最短路。路P0的权称为从vs到vt的距离，记为d(vs,vt),显然d(vs,vt)与d(vt,vs)不一定相等。,二、最短路算法,设G=为n阶带权图，wij0,若vi与vj不相邻，令wij=,标号法：标号法是由E.W.Dijkstra于1959年提出来的，其基本思想是：从vs出发，逐步地向外探寻最短路。在执行过程中，与每点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路的权（称为P标号），或者表示从vs到该点的最短路的权的上界（称为T标号），方法的每步是去修改T标号，并把某个T标号的点改变为具有P标号的点，从而使G中具有P标号的顶点数多一个，这样，至多经过p1步，就可以求出从vs到各点的最短路。,以引例为例，说明标号法的基本思想。,s=1,因所有wij0，故d(v1,v1)=0,这时v1是具有P标号的点。,考察从v1出发的三条弧(v1,v2),(v1,v3),(v1,v4)。如果从v1出发沿(v1,v2)到达v2,则需要d(v1,v1)+w12=6单位费用；如果,从v1出发沿(v1,v3)到达v3，则需要d(v1,v1)+w13=3单位费用；类似地若沿(v1,v4)到达v4,则需要d(v1,v1)+w14=1单位费用。由于mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14=d(v1,v1)+w14=1所以从v1出发到达v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1,v4)，d(v1,v4)=1。v4变成具有P标号点。,考察从v1及v4指向的其余点的弧，由上已知，从v1出发分别沿(v1,v2)，(v1,v3)到达v2,v3,所需6，3单位费用，而从v1出发沿(v1,v4)和(v4,v6)到达v6,所需费用是d(v1,v4)+w46=1+10=11单位。因为mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d(v1,v1)+w13=3,所以从v1出发到达v3所需要的最小费用必定是3单位，即从v1到v3的最短路是(v1,v3)，d(v1,v3)=3。v3变成具有P标号点。如此重复此过程，可以求出从v1到任意一点的最短路。,几个记号：用P，T分别表示某点具有P标号，T标号，用Si表示第i步时具有P标号点的集合。在每个点v处给一个值(v)。如果算法结束时，(v)=m，表示从vs到v的最短路上，v的前一个点是vm；如果(v)=M，则表示G中不含从vs到v的最短路；如果(v)=0，则表示v=vs。,Dijkstra方法的步骤：,开始（i=0）令S0=vs,P(vs)=0,(vs)=0,对每个vvs,令T(v)=+,(v)=M，令k=s。,（1）如果Si=V，算法终止，这时，对每个vSi,d(vs,v)=P(v);否则转（2）,（2）考察每个使(vk,vj)E,且vjSi的点vj。,如果T(vj)P(vk)+wkj,则把T(vj)修改为P(vk)+wkj,把(vj)修改为k；否则转入（3）。,(2)因为(v1,v2)E,且v2S0,P(v1)+w12T(v2),把T(v2)修改为P(v1)+w12=6,(v2)修改为1；,同理，把T(v3)修改为P(v1)+w13=3,(v3)修改为1；把T(v4)修改为P(v1)+w14=1,(v4)修改为1。,（3）在所有的T标号中，T(v4)=1最小，令P(v4)=1,令S1=S0v4,k=4。,（3）在所有的T标号中，T(v3)=3最小，令P(v3)=3,令S2=v1,v4,v3,k=3。,（3）在所有的T标号中，T(v2)=5最小,令P(v2)=5,令S3=v1,v4,v3,v2,k=2。,算法终止时：d(v1,vi)=P(vi),i=1,2,8;从v1到v9不存在路。,最短路：(v1,v3,v2,v5,v8)d(v1,v8)=12,例2求右图所示带权图中从v1到v8的最短路,解：这里只给出结果P(v1)=0,P(v4)=1,P(v3)=3,P(v2)=5,P(v5)=6,P(v9)=8,P(v7)=9,P(v6)=10,P(v8)=11;(v1)=0,(v4)=1,(v3)=1,(v2)=3,(v5)=2,(v9)=5,(v7)=5,(v6)=5,(v8)=9。,最短路：(v1,v3,v2,v5,v9,v8),d(v1,v8)=11,例3求右图中从v0到v5的最短路,用标号法解题时，可将计算过程用一张图表来表示。,最短路：T=v0v1v2v4v3v5,例3设备更新问题某企业使用一台设备，每年年初，经理就要决定是购置新设备，还是继续使用旧的。若购置新设备，就要支付一定的购置费；若继续使用旧的，则需要支付一定的维修费。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。