5-2最短路问题.ppt

《5-2最短路问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路问题Shortest-PathProblem单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求总路程最短的线路。v1v4v2v8v7v6v5v9636234102312624101v3一、问题的提法及应用背景（1）问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。（注意：在有向图中，通路——开的初等链中所有的弧应是首尾相连的。）（2）应用背景——路径寻优、管道铺设、线路安排、厂区布局、设备更新等。二、最短路算法标号法（Dijkstra算

2、法）两个固定点之间的最短路距离矩阵法海斯算法任意点之间的最短路二、最短路算法：1．D氏标号法（Dijkstra）（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。（2）使用条件——网络中所有的弧权均非负，即。（3）选用符号的意义：①标号P（固定标号或永久性标号）——从始点到该标号点的最短路权。②标号T（临时性标号）——从始点到该标号点的最短路权上界。Step-2：考虑满足条件①的所有点；②具有T标号，即，S为T标号点集。修改的T标号为，并将结果仍记为；Step-1：始点标上固定标号p(v1=0),其余各

3、点标临时性标号T(vj)=,j1;Step-3：若网络图中已无T标号点，停止计算。否则,令,然后将的T标号改成P标号，转入第二步。注意将第二步中的改为。（4）计算步骤例14v1v2v3v4v6v5v722561413412解：先将网络用矩阵形式表示:步骤考察点T标号点集标号（表P标号）1v1{v2，…，v7}v1v2v3v4v5v6v70------0+20+525----23456v2v3v4v5v6{v3，…，v7}{v4，…，v7}{v5，v6，v7}{v5，v7}2+22+42+6468--4+14+3587-5+45+

4、15+48696+288{v7}8+18反向追踪，得到最优路线：v1v2v3v4v6v7v51)若先把v7的标号改为永久性标号，该怎麽继续作下去？2)e47=2?1)单点到所有点的最短路？2)最短路径？最短路值？56v6v7{v5，v7}{v5}v1v2v3v4v5v6v76+2888+18869反向追踪，得到相同的最优路线。在得到从起点到终点的最短路长的同时，还能得到什麽附加信息？能得到从（起点）到各点的最短路线和最短路长。Dijkstra算法几点说明计算停止判别标准：对于求VS→Vt的最短路，Vt标上P标号时计算停止；对于求VS

5、→所有点的最短路，所有点标上P标号时计算停止。（1）路权为负值时失效（交通网络中一般不存在）（2）对于无向图—（将原图中的每条边视为由方向相反的两条弧组成，其权相等。Dijkstra最短路算法的特点和适应范围一种隐阶段的动态规划方法每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种深探法被框住的永久标记Tj表示vs到vj的最短路，因此要求dij0，第k次迭代得到的永久标记，其最短路中最多有k条边，因此最多有n1次迭代可以应用于简单有向

6、图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第n1次迭代后仍有节点的标记为，则表明vs到该节点无有向路径如果只求vs到vt的最短路，则当vt得到永久标记算法就结束了；但算法复杂度是一样的应用Dijkstra算法n1次，可以求所有点间的最短路vs到所有点的最短路也是一棵生成树，但不是最小生成树2.海斯算法（1）海斯算法的思想利用vi到vj的一步距离求出vi到vj的两步距离,再由两步距离求出四步距离,经有限步迭代即可求得vi到vj的最短路线和最短距离。（2）海斯算法的特点能求出网络中的点两两之间的最短距离；算法效

7、率较高，m次迭代即可完成计算；适用条件——无负回路的任意网络；（2）算法步骤：令则是指vi到vj的一步距离；当已知时,令则当m=1时，是vi到vj走两步的最小距离；当m=2时，是vi到vj走四步的最小距离；一般，是vi到vj走2m步的最小距离；当对所有I,j有:时,则是vi到vj的最短距离。因最短路线上最多有n-1条边，当2mn-1时,上述结论成立。v1v2v3v4v5v6268395331写出其距离矩阵第一轮迭代：按照迭代公式进行计算，求得矩阵D（1）=(dij(1))第一行计算示例：取自第1列（第1行+第2列）取自第2列

8、（第1行+第3列）取自第2列（第1行+第4列）取自第3列（第1行+第5列）（第1行+第6列）相应的中间点矩阵：第二轮迭代：由D（1）按公式迭代得D(2)第三轮迭代：由D(2)按公式迭代得D(3)由于D(2)=D(3)，故D(3)中的元