最短路模型课件

1、关于最短路模型第一张，PPT共十二页，创作于2022年6月一、引例例1：已知如图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需的费用。现在某人要从v1出发通过这个交通网到v8 ，求使总费用最小的旅行路线。对于有向图G 或无向图G 的每一条边e ，附加一个实数w(e),则称w(e)为边e 上的权，当e=(vi,vj)时，w(e)也可记为wij 。G 连同其各边上的权称为带权图，带权图常记为G=。最短路问题：设G 是带权图，vs,vt是G 的两个顶点，P是G 中从vs到vt的一条通路，定义路P 的权为P 中所有边的权之和，记为w(P)。最短路就是在所有从vs到vt的路中，求一条权最小的路，

2、即求一条从vs到vt的路P0,使v6v5v4v3v2v1v9v8v7310461022161234263第二张，PPT共十二页，创作于2022年6月上式中对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到该点

3、的最短路的权（称为P 标号），或者表示从vs 到该点的最短路的权的上界（称为T 标号），方法的每步是去修改T 标号，并把某个T 标号的点改变为具有P 标号的点，从而使G 中具有P 标号的顶点数多一个，这样，至多经过p1步，就可以求出从vs到各点的最短路。以引例为例，说明标号法的基本思想。第三张，PPT共十二页，创作于2022年6月s =1,因所有wij0，故d(v1,v1)=0, 这时v1 是具有P 标号的点。v6v5v4v3v2v1v9v8v7310461022161234263考察从v1出发的三条弧(v1,v2), (v1,v3),(v1,v4) 。如果从v1出发沿(v1,v2)到达v2,

4、则需要d(v1,v1)+w12=6单位费用；如果从v1出发沿(v1,v3)到达v3 ，则需要d(v1,v1)+w13=3单位费用；类似地若沿(v1,v4)到达v4 , 则需要d(v1,v1)+w14=1单位费用。由于min d(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

5、 ，3单位费用，而从v1出发沿(v1,v4)和(v4,v6)到达v6 ,所需费用是d(v1,v4)+w46=1+10=11单位。因为min d(v1,v1)+w12 , d(v1,v1)+w13 , d(v1,v4)+w46= d(v1,v1)+w13=3第四张，PPT共十二页，创作于2022年6月所以从v1出发到达v3所需要的最小费用必定是3 单位，即从v1到v3的最短路是(v1,v3) ，d(v1,v3)=3 。v3变成具有P 标号点。如此重复此过程，可以求出从v1到任意一点的最短路。几个记号：用P ，T 分别表示某点具有P 标号，T 标号，用Si 表示第i 步时具有P 标号点的集合。在每

6、个点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 ,对每个v vs ,令T(v)=+, (v)=M ，令k = s 。（1）如果Si =V ，算法终止，这时，对每个v Si ,d(vs ,v) =P(v);否则转（2）（2）考察每个使(vk ,vj) E ,且vj Si 的点vj 。第五张，PPT共十二页，创作于2022年6月如果

7、T(vj)P(vk) +wkj ,则把T(vj) 修改为P(vk) +wkj ,把 (vj) 修改为k；否则转入（3） 。v6v5v4v3v2v1v9v8v7310461022161234263i=0 : S0=v1 , P(v1) = 0 , (v1) =0 ,T(vi)=+, (v) =M ,(i =2,3, ,9) , k=1(2)因为(v1 ,v2) E ,且v2 S0, 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,

8、(v4)修改为1 。第六张，PPT共十二页，创作于2022年6月v6v5v4v3v2v1v9v8v7310461022161234263（3）在所有的T 标号中，T(v4)=1最小，令P(v4)=1,令S1=S0v4 , k=4 。i=1 : (2)把T(v6)修改为P(v4)+w46=11 , (v6)修改为4 （3）在所有的T 标号中，T(v3)=3最小，令P(v3)=3,令S2=v1,v4,v3 , k=3 。i=2 : (2)把T(v2)修改为P(v3)+w32=5 , (v2)修改为3 （3）在所有的T 标号中，T(v2)=5最小,令P(v2)=5,令S3=v1,v4,v3,v2 ,

9、 k=2 。i=3 : (2)把T(v5)修改为P(v2)+w25=6 , (v5)修改为2 （3）在所有的T 标号中，T(v5)=6最小,令P(v5)=6 , 令S4=v1,v4,v3,v2,v5 , k=5 。第七张，PPT共十二页，创作于2022年6月i=4: (2)把T(v6) ,T(v7) ,T(v8)分别修改为10，9，12 ； (v6)， (v7)， (v8)修改为5 （3）在所有的T 标号中，T(v7)=9最小,令P(v7)=9 , 令S5=v1,v4,v3,v2,v5 ,v7 , k=7 。v6v5v4v3v2v1v9v8v7310461022161234263i=5: (2

10、)因T(v8)P(v7)+w78 , 所以T(v8)不变（3）在所有的T 标号中，T(v6)=10最小,令P(v6)=10 , 令S6=v1,v4,v3,v2,v5 ,v7 ,v6 , k=6 。i=6: 在所有的T 标号中，T(v8)=12最小,令P(v8)=12 , 令S7=v1,v4,v3,v2,v5 ,v7 ,v6,v8 , k=8 。i=7: T(v9)=+ ，算法终止。算法终止时：d(v1,vi)=P(vi) , i =1 ,2 , , 8 ;从v1到v9不存在路。最短路：(v1,v3,v2,v5,v8)d(v1,v8)=12第八张，PPT共十二页，创作于2022年6月v6v5v4

11、v3v2v1v9v8v73461022161234263例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 的最短路用标号法解题时，可将计算过程用一张图表来表示。v5357421126v4v1v2v0v3第九张，PPT共十二页，创作于2022年6月357421126v4v1v2v0v3最短路：T=v0v1v2v4v3v5 vk i v0 v1 v2 v3 v4 v501234501 1/v0433/v1+8877/v4+ 644/v2+ + + 1099/v3第十张，PPT共十二页，创作于2022年6月例3 设备更新问题某企业使用一台设备，每年年初，经理就要决定是购置新设备，还是继续使用旧的。若购置新设备，就要支付一定的购置费；若继续使用旧的，则需要支付一定的维修费。现在的问题是如何制