最短路邮递员问题.ppt

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