最短路问题算法精.ppt

《最短路问题算法精.ppt》由会员分享，可在线阅读，更多相关《最短路问题算法精.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最短路问题算法第1页，本讲稿共13页分析：设G=（V，E）是一个有向图，它的每一条边（U，V）都有一个权W（U，V），在G中指定一个结点V0，要求把从V0到G的每一个结点Vj(V)的最短有向路找出来（或者指出不存在从V0到Vj的有向路，即V0不可达Vj）。这个问题即为单源最短路问题。解决单源最短路径的基本思想是把图中所有结点分为两组，每一个结点对应一个距离值第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度；第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度；我们按最短路径长度递增的顺序把第二组的结点加到第一

2、组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。具体作法是：初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点）然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值vm的距离值+Wmi），则要修改vi的距离（vi的距离值vm的距离值+Wmi）。修改后再选距离值最小的一

3、个结点加入到第一组中，。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。第2页，本讲稿共13页设 n图的结点数；adj有向图的相邻矩阵。其中 dist最短路径集合。其中 distipre在v0至vi的最短路径上，vi的前趋结点序号；distilengthv0至vI的最短路径长度，即vi的距离值；（1in）Const n=图的结点数；Type path=record 路径集合的结点类型 length：real；距离值 pre：0n；前趋结点序号 end；var adj：array1n，1n of real 相邻

4、矩阵 dist：array1n of path；路径集合第3页，本讲稿共13页计算单源最短路径的过程如下：fillchar(adj，sizeof(adj)，0)；建立相邻矩阵adj for i1 to n do for j1 to n do if（i，j）E then adji，jwij else adji，j；for i1 to n do 路径集合初始化 begin distilengthadjv0，i；if distilength then distiprev0 else distipre0；end；for adjv0，v01；源结点v0进入第一组repeat min；u0；for i1

5、to n do 从第二组中找距离值最小的结点u if(adji，i=0)and(distilengthmin)then begin ui；mindistilength；end；thenif u0 第二组中存在一个距离值最小的结点 then begin adju，u1；结点u进入第一组 for i1 to n do 修正第二组中u可达的结点距离值 if(adji，i=0)and(distilengthdistulength+adju，i)then begin distilengthdistulength+adju，i；distipreu；end；then end；then until u=0；第

6、4页，本讲稿共13页算法结束时，沿着结点vi的pre指针回溯，便可确定v0至vi的最短路径：procedure print(i：integer)；begin if i=v0 then 输出结点v0 else begin print(distipre)；输出结点i和v0至vi的最短路径长度distilength；end；else end；print显然递归调用print1，printn后，可得知v0至所有结点的最短路径。由此得出主程序：输入城镇数n；输入出发城镇序号v0；输入城镇间的距离矩阵w；计算单源最短路径方案dist；for i1 to n do 枚举除v0外的其它城镇begin if(i

7、v0)and(distilength)若城镇i与城镇v0间有通路，则输出它们之间的最短距离和路径方案then begin wrtiln(distilength)；print(i)；end；thenwrteln；end；for第5页，本讲稿共13页位图位图给定一个n*m的矩形位图，位图中的每个像素不是白色就是黑色，但至少有一个是白色的。第i行、第j列的像素被称作像素(i，j)。两个像素p1=(i1，j1)，p2=(i2，j2)之间的距离定义为：d(p1，p2)=|i1-i2|+|j1-j2|。现在请你计算图中每个像素与离其最近的“白像素”的距离。【输入输入】输入文件BIT.IN的第一行包含两个整

8、数n，m（1n150，1m150），用一个空格隔开。接下来n行，每一行都包含一个长度为m的01串；第i+1行，第j列的字符若为1，则像素(i，j)是白色的；否则是黑色的。【输出输出】文件BIT.OUT包含n行，每行有m个用空格隔开的整数。第i行、第j列的整数表示(i，j)与离它最近的白像素之间的距离。第6页，本讲稿共13页算法分析算法分析1.由于是求所有黑像素的点到白像素的最短距离，所以采用适合于整体计算floyd算法比较好，但floyd算法的时间复杂度为O（n3m3），不能满足时间要求。2.考虑用求单源最短路径的算法：对于每一点进行一次宽度优先搜索，求该点到其他各点的最短距离。但这一算法的时

9、间复杂度也达到了O（n2m2），3.在前面的方法里，我们是将每个黑像素到白像素的距离作为单独的问题来考虑的。这里忽略了一个重要的信息：相邻的黑像素之间有着很强的联系。定义：f（x，y）表示像素（x，y）到最近的白像素的距离。f（x，y）=minf（x-1，y），f（x+1，y），f（x，y-1），f（x，y+1）+1 看到了这个式子，眼前顿时豁然开朗：前面所用的宽度优先搜索是以黑像素作为源点，得到的是单源最短路；而现在以白像素作为源点，求的是多源最短路。采用多源最短路径的算法求解本题，时间复杂度仅为O（n*m），时效大为改善。第7页，本讲稿共13页设constmaxn=150；位图的规模mov

10、e：array1.4，1.2 of integer=(1，0)，(0，1)，(-1，0)，(0，-1)；四个方向所对应的水平竖直增量varused：array1.maxn，1.maxn of boolean；像素已访问标志list：array1.maxn*maxn，1.2 of integer；listi为第i个源点(白像素)的坐标map：array1.maxn，1.maxn of integer；mapi，j为（i，j）的像素离最近白像素的距离i，j，n，p，q，x，y，t1，t2，m：integer；n、m为bit图的规模，p，q为队列的首尾指针第8页，本讲稿共13页readln(n，m)

11、；读bit图的规模p：=1；q：=0；队列的首尾指针初始化for i：=1 to n do begin 读入bit图，白像素作为源点入队 for j：=1 to m do begin read(ch)；if ch=1 then begin inc(q)；listq，1：=i；listq，2：=j；usedi，j：=true；mapi，j：=0；（i，j）的白像素已访问,离最近白像素的距离初始化 end；thenend；forreadln；end；for第9页，本讲稿共13页while p=q do begin 通过宽度优先搜索求出各个像素到最近白像素的距离 x：=listp，1；y：=list

12、p，2；队首的白像素坐标出队 for i：=1 to 4 do begin 搜索四个相邻方向 t1：=x+movei，1；t2：=y+movei，2；计算i方向的相邻坐标 if(t1=n)and(t2=1)and(t2=1)and(not usedt1，t2)then begin 若该坐标在界内且未访问，则入队、设访问标志，并计算该像素离最近白像素的距离inc(q)；listq，1：=t1；listq，2：=t2；usedt1，t2：=true；mapt1，t2：=mapx，y+1；end；then end；for inc(p)；出队end；whilefor i：=1 to n do 输出每一

13、个像素离最近白像素的距离 begin for j：=1 to m do write(mapi，j，)；writeln；end；for第10页，本讲稿共13页例题：货币兑换例题：货币兑换 若干个货币兑换点在我们的城市中工作着。每个兑换点只能进行两种指定货币的兑换。不同兑换点兑换的货币有可能相同。每个兑换点有它自己的兑换汇率，货币A到货币B的汇率表示要多少单位的货币B才能兑换到一个单位的货币A。当然货币兑换要支付一定量的中转费。例如，如果你想将100美元兑换成俄元，汇率是29.75，中转费为0.39，那么你会兑换到(100-0.39)29.75=2963.3975俄元。城市中流通着N(N100)类

14、货币，用数字1至N标号表示。每个货币兑换点用6个数字来描述：整数A和B是兑换货币的编号，实数RAB，CAB表示A兑换成B的汇率和中转费用，RBA，CBA表示B兑换成A的汇率和中转费用。Nick有一些第S类货币，他想在若干次交换后增加他的资金，当然这些资金最终仍是第S类货币。请你告诉他该想法能否实现。第11页，本讲稿共13页构图将N种货币看成N个顶点，将每个兑换点转化为两条有向边。根据兑换公式，目前从A货币兑换到B货币的汇率和中转费用为RAB，CAB，那么由对应的A顶点向B顶点连一条有向边，从A点得到的B的可能最大值为：(A目前的最大值-CAB)RAB。注意，这里所求的是最大值，为了转化为最短路

15、，我们可以在数字前面加上一个负号。第12页，本讲稿共13页 1、利用求最短路的方法求最长路。由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，必须采用Bellman-Ford算法。2、需要指出一点，无论是求负权最短路还是求最长路，可能遇到的一个问题是可能存在环，从而导致货币最大值不存在（因为可以沿环使最大值不断增大）。解决的办法其实很简单，我们只需要设立一个停止条件就行了：如果当前没有顶点的最优值可以更新，或者第S个点的最优值已经优于初始值，则退出循环。3、两点间的边可能不止一条，所以图的存储结构不宜采用相邻矩阵（从效率的角度也不提倡用），而应该采用邻接表；4、由于涉及比较实数的大小，所以判断AB应该写成A+ZeroB，判断AB应该写成A-ZeroB，其中Zero是一个很小的数，具体值要根据实际情况设定，例如设为1e-8。第13页，本讲稿共13页