最短路模型.ppt

《最短路模型.ppt》由会员分享，可在线阅读，更多相关《最短路模型.ppt（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关于最短路模型现在学习的是第1页，共12页一、引例一、引例例例1：已知如图所示的单行线交通网，每：已知如图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需的弧旁的数字表示通过这条单行线所需的费用。现在某人要从费用。现在某人要从v1出发通过这个交通出发通过这个交通网到网到v8，求使总费用最小的旅行路线。，求使总费用最小的旅行路线。对于有向图对于有向图G 或无向图或无向图G 的每一条边的每一条边e，附加一个实数，附加一个实数w(e),则称则称w(e)为边为边e 上的权，当上的权，当e=(vi,vj)时，时，w(e)也可记为也可记为wij。G 连同其各边上的权称为带权图连同其各边上的权称为带权

2、图，带权图常记为，带权图常记为G=。最短路问题：设最短路问题：设G 是带权图，是带权图，vs,vt是是G 的两个顶点，的两个顶点，P是是G 中从中从vs到到vt的一条通路，定义路的一条通路，定义路P 的权为的权为P 中所有边的权之和，记为中所有边的权之和，记为w(P)。最短。最短路就是在所有从路就是在所有从vs到到vt的路中，求一条权最小的路，即求一条从的路中，求一条权最小的路，即求一条从vs到到vt的路的路P0,使使)(min)(PwPwP 0v6v5v4v3v2v1v9v8v7310461022161234263现在学习的是第2页，共12页上式中对上式中对G 中所有从中所有从vs到到vt的

3、路的路P 取最小，称取最小，称P0为从为从vs到到vt的最短路。路的最短路。路P0的权的权称为从称为从vs到到vt的距离，记为的距离，记为d(vs,vt),显然显然d(vs,vt)与与d(vt,vs)不一定相等。不一定相等。二、最短路算法二、最短路算法设设G=为为n阶带权图，阶带权图，wij 0,若若vi与与vj 不相邻，令不相邻，令wij=标号法：标号法是由标号法：标号法是由E.W.Dijkstra于于1959年提出来的，其基本思想是：从年提出来的，其基本思想是：从vs出发，逐步地向外探寻最短路。在执行过程中，与每点对应，记录下一出发，逐步地向外探寻最短路。在执行过程中，与每点对应，记录下一

4、个数（称为这个点的标号），它或者表示从个数（称为这个点的标号），它或者表示从vs到该点的最短路的权（称为到该点的最短路的权（称为P 标号），或者表示从标号），或者表示从vs 到该点的最短路的权的上界（称为到该点的最短路的权的上界（称为T 标号），方法标号），方法的每步是去修改的每步是去修改T 标号，并把某个标号，并把某个T 标号的点改变为具有标号的点改变为具有P 标号的点，从而使标号的点，从而使G 中具有中具有P 标号的顶点数多一个，这样，至多经过标号的顶点数多一个，这样，至多经过p1步，就可以求出从步，就可以求出从vs到各到各点的最短路。点的最短路。以引例为例，说明标号法的基本思想。以引例为

5、例，说明标号法的基本思想。现在学习的是第3页，共12页s=1,因所有因所有wij 0，故，故d(v1,v1)=0,这时这时v1 是具有是具有P 标号的点。标号的点。v6v5v4v3v2v1v9v8v7310461022161234263考察从考察从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)到达到

6、达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，3单位费用，而从单位费用，

7、而从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现在学习的是第4页，共12页所以从所以从v1出发到达出发到达v3所需要的最小费用必定是所需要的最小费用必定是3 单位，即从单位，即从v1到到v3的最短路是的最短路是(v1,v3)，d(v1,v3)=3。v3变成具有变成具有P 标号点。如此重复此过程，可以求出从标号点。如此重复此过程，可以求出从v1到任到任意一点的最短路。意一点的最短路。几

8、个记号：用几个记号：用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,对每

9、个对每个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。现在学习的是第5页，共12页如果如果T(vj)P(vk)+wkj,则把则把T(vj)修改为修改为P(vk)+wkj,把把 (vj)修改为修改为k；否则转；否则转入（入（3）。)(),(,),(),(,),()(,)()(min)()(vTvvdSvvPvvdviijvSSvTvPPTvvTvTvTsisijiijjjjjSvjii

10、iiiiji而而对对每每个个这这时时对对每每个个）；否否则则终终止止，转转入入（换换成成把把令令标标号号，标标号号变变为为的的则则把把如如果果令令i1S11,k 3v6v5v4v3v2v1v9v8v7310461022161234263i=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)修改为

11、修改为P(v1)+w14=1,(v4)修改为修改为1 。现在学习的是第6页，共12页v6v5v4v3v2v1v9v8v7310461022161234263（3）在所有的）在所有的T 标号中，标号中，T(v4)=1最小，最小，令令P(v4)=1,令令S1=S0 v4,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）在所有的）在所有的

12、T 标号中，标号中，T(v2)=5最小最小,令令P(v2)=5,令令S3=v1,v4,v3,v2,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。现在学习的是第7页，共12页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,v

13、3,v2,v5,v7 ,k=7 。v6v5v4v3v2v1v9v8v7310461022161234263i=5:(2)因因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

14、=1,2,8;从从v1到到v9不存在路。不存在路。最短路：最短路：(v1,v3,v2,v5,v8)d(v1,v8)=12现在学习的是第8页，共12页v6v5v4v3v2v1v9v8v73461022161234263例例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)=

15、9。最短路：最短路：(v1,v3,v2,v5,v9,v8),d(v1,v8)=11例例3 求右图中从求右图中从v0到到v5 的最短路的最短路用标号法解题时，可将计算过程用一张图用标号法解题时，可将计算过程用一张图表来表示。表来表示。v5357421126v4v1v2v0v3现在学习的是第9页，共12页357421126v4v1v2v0v3最短路：最短路：T=v0v1v2v4v3v5 vk i v0 v1 v2 v3 v4 v501234501/v0433/v1+8877/v4+644/v2+1099/v3现在学习的是第10页，共12页例例3 设备更新问题设备更新问题某企业使用一台设备，每年年初

16、，经理就要决定是购置新设备，还是继续使用某企业使用一台设备，每年年初，经理就要决定是购置新设备，还是继续使用旧的。若购置新设备，就要支付一定的购置费；若继续使用旧的，则需要支付旧的。若购置新设备，就要支付一定的购置费；若继续使用旧的，则需要支付一定的维修费。现在的问题是如何制定一个几年之内的设备更新计划，使得总一定的维修费。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。我们用一个五年内要更新某设备的计划为例，若该种设备在的支付费用最少。我们用一个五年内要更新某设备的计划为例，若该种设备在各年年初的价格为下表各年年初的价格为下表1；还已知使用不同时间的设备所需维修费为下表；还已知使用不同时间的设备所需维修费为下表2。第第1年年第第2年年第第3年年第第4年年第第5年年1111121213使用年数使用年数0112233445维修费用维修费用5681118现在学习的是第11页，共12页感谢大家观看感谢大家观看现在学习的是第12页，共12页