最短路问题ppt课件.ppt

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

1、5-2.最短路问题一、问题的提法及应用背景（1）问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。（注意：在有向图中，通路——开的初等链中所有的弧应是首尾相连的。）（2）应用背景——管道铺设、线路安排、厂区布局、设备更新等。二、最短路算法：1．D氏标号法（Dijkstra）（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的(两层最小化的含义)。（2）使用条件——网络中所有的弧权均非负，即。（3）选用符号的意义：①标号P（固定标号或永久性标号）——从始点到该标号点的最短

2、路权。②标号T（临时性标号）——从始点到该标号点的最短路权上界。2.具体步骤：令：①对所有，求，将结果仍记为。代表任意节点到的最短距离。给到的所有最短距离赋初值（上限）刷新到一级近邻的最短距离。到其他不直接邻接的节点的最短距离不会发生变化。②在v1到所有其他节点的最短距离中选择最小的距离，找到节点vk，使下式满足：求满足令：比较v1到所有其它节点的最短距离，找到节点vk,并将最小的距离记录在P(vk)中。③如果已经搜索到最后一个节点即，那么就已经求出了到的最短距离；否则，令，从中删去，转①继续搜索。把k赋给i，从搜索节点集合中去

3、掉vk,重新搜索vk（将vk作为vi）到其余节点的最短距离。算法思想示意图例5-3用狄克斯拉算法求解图5-1所示最短路问题。4v1v2v3v4v6v5v722561413412图5-1例5-3网络图解：先将图5-1的网络用矩阵形式表示出来:初始值{0}∞∞∞∞∞∞第一次迭代0+20+5∞∞∞∞{2}5∞∞∞∞第二次迭代2+22+42+6∞∞{4}68∞∞第三次迭代4+14+∞4+3∞{5}87∞第四次迭代5+45+15+48{6}9第五次迭代6+∞6+2{8}8第6次迭代8+18如果选择v7,则k=7=n,迭代结束。8{8}反

4、向追踪，得到最优路线：v1v2v3v4v6v7v5讨论：若先把v7的标号改为永久性标号，会怎样？（5）D氏标号法（Dijkstra）的优缺点（获得的附加信息）：能得到从（起点）到各点的最短路线和最短路长。v1v2v323-5网络中有负权时，D氏标号法失效列表法（Ford算法）求从点到任何一点（）的最短路。（1）使用条件—没有负回路（2）步骤：①令，，其中为起点到的弧（）的权；③当迭代到第步，有时，收敛；就是从起点到各点的最短距离；④反向追踪求出最短路线。其中，表示从起点到点走k步的最短距离；②用下列递推公式进行迭代：例5-4：计

5、算下图中从vs到vt的最短路线和最短路长v2-1vsv1v3vt4-111326-2vsv1v2v3vt0----1------40-------11-20---------630------1---20041------0414504145vsv1v2v3vt最短路线为，最短路权为5。反向追踪寻找最短路线，得：=min（0+4，4+0，1+-，-+-，-+（-1））=4依此类推…计算过程详示：=min（0+0，4+-，1+（-1），-+-，-+-）=0v2vsvsv1…………反向追踪过程：寻求一点vk，使，本题中vk即为v1，

6、所以找到弧（v1，vt）；再寻求一点vi，使，这里，vi即为vs，所以找到弧（vs，v1）；于是得最短路线②优点：可以在有负权的情况下，寻求从起点到各个点的最短路线和最短路长。3.海斯算法（1）算法思想：利用vi到vj的一步距离求出vi到vj的两步距离,再由两步距离求出四步距离,经有限步迭代即可求得vi到vj的最短路线和最短距离。（2）算法步骤：令则是指vi到vj的一步距离；当已知时,令则当m=1时，是vi到vj走两步的最小距离；当m=2时，是vi到vj走四步的最小距离；一般，是vi到vj走2m步的最小距离；当对所有I,j

7、有:时,则是vi到vj的最短距离。由于最短路线上最多有n-1条边，因此，当2mn-1时,就是最短距离。（3）算法举例：例5-5用海斯算法求下面的网络图中从v1到v6的最短距离和最短路线。v1v2v3v4v5v6268395331写出其距离矩阵第一轮迭代：按照迭代公式进行计算，求得矩阵D（1）=(dij(1))第一行计算示例：取自第1列（第1行+第2列）经由在中间点矩阵中（i,j）的位置填上k取自第2列（第1行+第3列）取自第2列（第1行+第4列）取自第3列（第1行+第5列）（第1行+第6列）相应的（最佳）中间点矩阵：表示节点i到

8、节点j走步的距离中，经节点k到j，能使：第二轮迭代：由D（1）按公式迭代得D(2)第三轮迭代：由D(2)按公式迭代得D(3)由于D(2)=D(3)，故D(3)中的元素就是vi到vj的最短距离,D(3)称为最短距离矩阵。中转点中转点于是，得到由v1到v6的最短路线