最短路 邮递员问题.ppt

最短路问题
最短路问题是最重要的优化问题之一,
它不仅可以直接应用于解决生产实际的许多
问题例如各种管道的铺设、线路的安排、厂
区的布局、设备的更新等等,而且经常被作
为一个基本工具,用于解决其它优化问题如
运输网络的最小费用流等。
(最短距离、费时最少、费用最省)
定义(权、赋权图):对图G的每一条
边e,可赋与一个实数
W〔e)称为边e的权。图G连同它边上
的权称为赋权图。路中边权最小的称
为最短路
权可以表示铁路长度,通讯网络的造
价,网络中表示耗时等
狄克斯拉( Dijkstra)算法
最短路问题可以化为线性规划问题求解,也可以用动态规划方
法求解,这里介绍一种有效算法一狄克斯拉( Dijkstra)算法,这
算法是1959年首次被提出来的。该算法适用于每条弧的权数o:≥0
情形。算法的基本思路:从发点v出发,有一个假想的流沿网络
切可能的方向等速前进,遇到新节点后,再继续沿一切可能的方向
继续前进,则最先到达终点v的流所走过的路径一定是最短的。为
实现这一想法,对假想流依次到达的点,依次给予标号,表示v
到这些点的最短距离。对于假想流尚未到达的点给予T标号,表示v
到这些点的最短距离的估计值。具体作法如下:
1°标p(v)=0,其余点标T(v,)=+∞;
·2°由刚刚获得p标号的v点出发,改善它的相邻点v;的T标号,即
新的T(v)=mn{老的T(v),p(v)+
若7(v)=p(v)+0,则记k(v)=v(前点标记)
·3°找出具有最小T标号的点,将其标号改为p标号。若v已获得p
标号,则已找到最短路,由k(v2)反向追踪,就可找出v到v的最
短路径,p(v)就是v到v的最短距离。否则,转2°。
例求图中v到v的最短路。
5
解:标p(v)=0,其余点标T(v)=+∞,i=2,3,4,5,6,7,8
T(v2)=min{+∞0+3}=3,k(v2)
T(v3)=min{+∞0+5}=5,k(v2)=v
T(v)-min{+∞0+6}=6,k(v2)
将具有最小7标号的v2点的标号改为P标号:p(v2)=3
T(v3)=min{5,3+1}=4,k(v3)=v2
T(v)=min{+∞,3+7}=10,k(v)=
T(v)=min{+∞,31+4}-7,k(v6)="2
目前,点v3具有最小7标号,将其标号改为p标号:p(v)=4;
P
p(v
T(v)=min64+1}=5,k(v4)=
T(v)=min{7,4+2}=6,k(vn)=v
目前,点v具有最小T标号,将其标号改为p标号:p(v)=5
T(v)=min{65+3}=6;T(v)min{+∞,5+5}=10,k(vn)=v
目前,点v具有最小T标号,将其标号改为p标号:P(v)=6
T(v3)=min{+2}=8,k(vy)
T(v)=min{106+1}=7,k(v)=
T(v3)-min{+∞,6+9}-15,k(v3)=v6
日前,点v具有最小7标号,将其标号改为p标号:p(v)=7;
T(v3)=min{15,7+5}=12,k(v)=v;p(v)=8;
T(v)=min{12,8+6}=12,p(v)=12;反向追踪找最短路径。
最短路径为:v→→v→→→v;
因p(v)=12,所以v→v3的最短距离为12。
●最短路问题不仅可以求解交通图中两点之间的最短距离,实际
中很多问题也可变为最短路问题加以求解。例如设备更新问题,厂
区合理布局问题等。兹举一例
●例1(设备更新问题)某企业使用一台设备,在每年年底,企业
都要决策下年度是购买一台新设备呢?还是继续使用这台设备。若
购买新的,就要支付一笔购置费;如果使用旧设备,只要支付维修
费,而维修费随着设备的使用年限延长而增加。现根据以往统计资
料已经估算出设备在各年初的价格和不同使用年限的修理费用,分
别如表1、表2所示。
●试确定一个五年内的设备更新计划,使五年内总支出最小
图上标示法
下面我们结合例3介绍求解最短路问题的图上标示法,它比狄克
斯拉算法更简洁。
年份
四五
置费111121213
表2
使用年限0-11-22~33-44-5
年修理费5681118
解:先根据表1、表2的数据画出设备更新费用网络图,如下图
所示。图中点v表示第i年开始,弧(v,v)表示设备第i年初使用到
第年初,弧(v,n)上的权数表示该期间设备所需的费用。这样,
求五年内设备最优更新方案便转化为求v→v的最短路
攴d(v)表示点v到终点的最短距离,根据动态规划最优性原理,
最短路径中任何子