最短路径与标号法.doc

《最短路径与标号法.doc》由会员分享，可在线阅读，更多相关《最短路径与标号法.doc（19页珍藏版）》请在三一文库上搜索。

1、最短路径与标号法前面我们学习过动态规划的应用，图中没明显阶段求最短路径的问题属于无明显阶段的动态规划，通常用标号法求解，求最短路径问题是信息学奥赛中很重要的一类问题，许多问题都可转化为求图的最短路径来来解，图的最短路径在图论中有经典的算法，本章介绍求图的最短路径的dijkstra算法、Floyed算法，以及标号法。一、最短路径的算法1、单源点最短路径（dijkstra算法）给定一个带权有向图G=（V，E），其中每条边的权是一个非负实数，另外，还给定V中的一个顶点，称为源点。求从源点到所有其他各顶点的最短路径长度。这个问题称为单源最短路径问题。求单源最短路径可用dijkstra算法求解。（dij

2、kstra算法）算法思想：设源点为x0，disti表示顶点i到源点x0的最短路径长度，mapi,j表示图中顶点i到顶点j的长度，用数组mark对所有的顶点作标记，已求出源点到达该点J的最短路径的点J记为markj=true,否则标记为false。初始时，对源点作标记，然后从未作标记的点中找出到源点路径长度最短的顶点minj，对该顶点作标记，并对其它未作标记的点K作判断：if distminj+mapminj,kdistk then distk= distminj+mapminj,k。重复处理，直到所有的顶点都已作标记，这时求出了源点到所有顶点的最短路径。算法过程：const maxn=100;

3、var map: array1.maxn,1.maxn of integer; dist: array1.maxn of integer; mark: array1.maxn of Boolean; n,k: integer;procedure dijkstra; var I,j,min,minj,temp:integer; begin fillchar(mark,sizeof(mark),0); for I:=1 to n do disti:=maxint; distk:=0; for I:=1 to n-1 do begin min:=maxint; for j:=1 to n do if

4、 (not markj) and (distj0) then begin temp:=distminj+mapminj,j; if tempdistj then distj:=temp; end; end;end;以上只是求出了从源点到其它所有点的最短路径长度，所经过的具体路径没有保存，如果要求出具体的路径来，那么在求最短路径的过程中要将经过的中间点记录下来。下面通过例题来说明最短路径的求解。例1：最短路径问题下面给出某市各镇间路线网络图，市汽车站在市区A，现要求出市汽车站到各镇区的最短路径长度。 B 8 E 12 15 109 14 A 30 10 15 F 11 13 D C数据输入：从文

5、件city.dat中读入数据，第一行为镇区个数N，以下有N行，每行N个数据，在数据阵中，第i行第j列的数表示城镇i到城镇j的距离。最后一行为市区中心所在位置的编号。数据输出结果输出到文件city.out中，共有N-1行，每行由市区到达的镇区号、最短路径长度。输入输出样例city.dat60 12 11 30 0 012 0 9 14 8 1511 9 0 13 0 030 14 13 0 10 150 8 0 10 0 100 15 0 15 10 01city.out2 123 114 245 206 39分析：本题是典型的求单源最短路径问题，本直接用dijkstra算法求解。程序如下： p

6、rogram city;const maxn=100;var map: array1.maxn,1.maxn of integer; dist: array1.maxn of integer; mark: array1.maxn of Boolean; n,k: integer; first,i,j,min,minj,temp:integer; fin,fout:text;beginassign(fin,city.dat);assign(fout,city.out);reset(fin);rewrite(fout);readln(fin,n);for i:=1 to n do begin fo

7、r j:=1 to n do begin read(fin,mapi,j); if mapi,j=0 then mapi,j:=maxint;end; readln(fin); end;readln(fin,first);close(fin); fillchar(mark,sizeof(mark),0); k:=first; for I:=1 to n do disti:=mapk,i; distk:=0;markk:=true; for I:=1 to n-1 do begin min:=maxint; for j:=1 to n do if (not markj) and (distj0)

8、 then begin temp:=distminj+mapminj,j; if tempdistj then distj:=temp; end; end;for i:=1 to n do if ifirst then writeln(fout,i, ,disti);close(fout);end;2、所有顶点对之间的最短路径 Floyed算法设图G=（V，E），顶点I到顶点J的权为costI,j, 顶点I到 顶点J 的最短路径长度为AI，J，路径为PI，J。Floyed算法 算法思想：从任意顶点VI到VJ的路径上，每次增加一个顶点VK（K=1，2，, N），然后，比较增加VK后的路径是否比原

9、来的路径短，取其中短者作为从VI到的当前最短路径。当从取值到取值， 经过次这样的比较后，最终求得的就是任意两顶点和间的最短路径。算法过程：const n=50;typepathdata=array1.n,1.n of 0.n;mapdata=array1.n,1.n of integer;varp: pathdata; a:mapdata;procedure path(var p:pathdata; I,j:integer); var k:integer; begin k:=pI,j; if k0 thenbegin path(p,I,k); writeln(k); path(p,k,j);

10、end; end;procedure floyed(var a,cost:mapdata; var p:pathdata); var I,j,k:integer begin for I:=1 to n do for j:=1 to n do begin aI,j:=costI,j; pathI,j:=0; end; for k:=1 to n do for I:=1 to n do for j:=1 to n do if aI,k+ak,jaI,j then begin aI,j:=aI,k+ak,j; pI,j:=k; end; end;注意：dijkstra算法要求网中的权值都非负，否则，

11、算法虽可执行，但结果有误。而floyed算法则允许网中边上的权值为负，但不允许网中出现路径长度为负的回路。例2、哈利波特与魔法石石子路草地2341石子路森林提交文件：（ halibote.pas / halibote.exe ）大年初三的那个晚上，小可可去电影院看了哈利波特与魔法石，回到家坐在椅子上不一会儿就睡着了，并且梦见自己成了哈利波特驰骋在充满了正义与邪恶的宇宙中执著地为了正义而战。那天哈利波特去拯救Super samuel星球上的生灵，该星球上有七种不同的地形，依次分别是石子路、森林、草地、山地、雪地、沼泽和沙漠，用数字1-7表示，任意两个城市之间都存在至少一条通路，而且任意两个不经过

12、别的城市而直接通达的城市I和J之间都只存在一种地形T（I，J），奇怪的地，在Super samuel星球上哈利波特穿越地形U所用的时间与该地形的区域大小无关，去与地形U的区域中是否有魔法石有关，如果地形U的区域中没有魔法石，哈利波特要花费H（U）的时间才能穿越该区域，否则他只要花一半的时间就能穿越了，已知H（1）=2，H（2）=6，H（3）=4，H（4）=8，H（5）=6，H（6）=10，H（7）=14，S（U）=1表示地形U的区域中有魔法石，S（U）=0表示地形U的区域中没有魔法石。例如，如上图所示，有4对可以直接通达的城市（城市1与2、1与3、2与4、以及3与4）；S（1）0，S（2）1，

13、S（3）S（4）S（5）S（6）S（7）0，即只有森林中有魔法石，因此穿越森林所花费的时间是6/2=3，穿越石子路和草地的时间仍然分别是2和4。如果哈利波特想从城市1到城市4，则最快的路线是经过城市2，这条路线需要的时间是235。哈利波特总是忙于铲除邪恶、伸张正义，没有时间去寻找从起点城市I到终点城市J之间的最快路线。现在聘你作为哈利波特的助手编写程序寻找最快路线为哈利波特腾出更多的时间来将正义事业进行到底。数据输入：数据从文件halibote.dat读入，文件中第一行有七个数，分别是S（1）至S（7）；第二行有两个数，依次分别是起点城市I和终点城市J；第三行有一个正整数C，Cma then

14、ma:=j; if kma then ma:=k; se:=se+j+k; end; close(f);end;procedure main;var i,j,k:integer;begin for i:=1 to ma do for j:=1 to ma do if(i in se)and(ij)and(j in se)then begin for k:=1 to ma doif(ki)and(kj)and(mapi,k0)and(mapk,j0)and(mapi,k+mapk,jmapi,j) then begin mapi,j:=mapi,k+mapk,j;mapj,i:=mapi,j;e

15、nd; end;end;procedure print;begin assign(f,halibote.out); rewrite(f); writeln(f,mapx,y); close(f);end;beginreadin;main;print;end.二、标号法前面我们学习了求图的最短路径的两种算法，标号法是一种求图的最短路径的不用重复回溯搜索的高效率算法。一、标号法的算法思想 在图G中，顶点Vi到Vj的非负长度为Map(i,j)，求从起点Vs到终点Ve的最短距离。 设：x数据为扩展的队列；Sum(j)表示顶点Vs到Vj的最短距离，FA(j)表示顶点Vj的前趋结点，算法过程如下： （1）

16、队列初始化，Vs进入队列L，X1:=s, sum1=0；（2）取队首结点VK，若VK是目标结点Ve，则输入结果（最短路径值及路径），程序结束；否则继续（3）；（3）由VK扩展出结点VJ（结点VK与VJ相连），计算代价值若Sum(k)+mapk,jsum(j) 则替换结点J的代价，换代价值由小到大插入队列，并记录其父结点：sum(j):=sum(k)+mapk,j, faj:=k，结点J入队列继续（2），否则直接转（2）。注意：1.只有两个顶点间的距离为非负时，才可用标号法。 2.只有队列的首结点是目标结点时，才可停止计算。否则得出的不一定是最优解。标号法算法伪代码如下：fillchar(x,s

17、izeof(x),0);for I:=1 to n do begin sumI:=maps,I; faI:=s; end;x1:=s; sums:=0;open:=1;close:=1;fas:=0;repeat temp:=xopen; if temp=Ve then print调用输出结果过程; halt; for j:=1 to n do if (sumtemp+maptemp,j0) thenbegin sumj:=sumtemp+maptemp,j;close:=close+1; 按代价由小到大将结点J插入队列； faj:=open;end;open:=open+1;until op

18、enclose例3：Car的旅行路线 问题描述又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。图例 机场 高速铁路飞机航线 注意：图中并没有标出所有的铁路与航线。那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。任务 找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。输入文件：键盘输

19、入文件名输 出：到屏幕(输出最小费用，小数点后保留2位。)输入格式 第一行为一个正整数n(0=n=10)，表示有n组测试数据。 每组的第一行有四个正整数s，t，A，B。S(0S=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1=A，BTmp_Value) or (Linei.Son=0); if Linei.Son=0 then begin Linei.Son:=Tail; LineTail.Father:=i; LineTail.Son:=0; end else begin LineTail.Fahter:=Linei.Father; LineTail.S

20、on:=i; Linei.Father:=Tail; end; end else begin end; end; end; until Fintout;end;procedure Made_The_4th_Point;var i,j,P1,P2,P3:integer; Max:real;begin Max:=0; for i:=(d-1)*4+1 to (d-1)*4+2 do for j:=i+1 to (d-1)*4+3 do if Get_Length(i,j)Max then begin Max:=Get_Length(i,j); P1:=i; P2:=j; end; P3:=(d-1

21、)*4*3+6-P1-P2; Airportd*4.x:=AirportP1.x+AirportP2.x-Airportp3.x; Airportd*4.y:=AirportP1.y+AirportP2.y-Airportp3.y;end;begin assign(RF,ReadFile); reset(RF); readln(RF,n); for c:=1 to n do begin readln(RF,s,t,A,B); for d:=1 to s do begin for e:=1 to 3 do read(RF,Airport(d-1)*4+e.x,Airport(d-1)*4+e.y

22、); Made_The_4th_Point; read(RF,Railwayc); end; Head:=0; Tail:=4; for d:=1 to 4 do begin Lined.Father:=0; Lined.Son:=d+1; Lined.Airport:=A*4-4+d; Lined.Value:=0; end; Line4.Son:=0; Main; end; close(RF);end.三、练习1、最佳路线问题描述塞内加尔是非洲的一个小国家，你也许很难在世界地图上找到它，甚至你有可能从未听说过它-它实在是个太小、太贫穷的国家了。可是，就是这个人口不足900万、全国仅有2个标

23、准足球场地的小国，在2002韩日世界杯的非洲区预选赛中脱颖而出，取得了世界杯决赛圈的入场券（幸好，去年中国队也进入了世界杯决赛圈，不然可就丢脸了）。在塞内加尔全国球迷欣喜若狂，世界足球行家大跌眼镜的同时，塞内加尔足协却发现自己面临着一个颇为尴尬的问题-说起来令人不可思议，由于打非洲区预选赛时四处征战，加上足协经营不力，现在足协的预算以几近赤字-也就是说，塞内加尔足协支付不起从本国乘飞机到达韩国参加世界杯的费用！经过三思，塞内加尔足协向非洲足联递交了一份关于减免球队旅行费用的申请；可是-众所周知的，非洲足联也是惨淡经营，幸好非洲足联秘书长神通广大，弄来了M张优惠乘机券：每张优惠券可以作用于一条航

24、线，使全队通过此航线的费用减半；多张优惠券用于同一条线路，其效果叠加-即在一条航线上用两张优惠券，其费用降为原费用的1/4，依此类推。 【问题】塞内加尔足球队要从塞内加尔国家机场出发，途经一些中转机场，最后要到达韩国釜山机场。为了合理地分配各张优惠券，使得所需费用最少，塞内加尔足协找到了你，请你编程解决这个问题。【输入】第1行有两个数N、M（0N=70，0=M连接（参见样例输出）；输入数据保证从塞内加尔机场可达釜山机场。【样例输入】5 20 0 80 96 070 0 72 54 018 0 0 99 8272 18 71 0 069 0 0 70 0【样例输出】81.001-3-52、邀请卡

25、分发AMS公司决定在元旦之夜举办一个盛大展览会，将广泛邀请各方人士参加。现在公司决定在该城市中的每个汽车站派一名员工向过往的行人分发邀请卡。但是，该城市的交通系统非常特别，每条公共汽车线路都是单向的，且只包含两个车站，即起点站与终点站，汽车从起点到终点站后空车返回。假设AMS公司位于1号车站，每天早上，这些员工从公司出发，分别到达各自的岗位进行邀请卡的分发，晚上再回到公司。请你帮AMS公司编一个程序，计算出每天要为这些分发邀请卡的员工付的交通费最少为多少？ 输入格式：输入文件的第一行包含两个整数P和Q （1=P,Q=50000）。P为车站总数（包含AMS公司），Q为公共汽车线路数目。接下来有Q

26、行，每行表示一条线路，包含三个数：起点，终点和车费。所有线路上的车费是正整数，且总和不超过1000000000。并假设任何两个车站之间都可到达。输出格式：输出文件仅有一行为公司花在分发邀请卡员工交通上的最少费用。输入输出样例样例1：输入2 21 2 132 1 33输出46样例2：输入4 61 2 102 1 601 3 203 4 102 4 54 1 50输出2103、恶魔城问题描述：上帝需要创造一位战士去消灭撒旦，这位战士必须要穿过恶魔城才能与撒旦决斗。恶魔城内有M条连接N个路口（从1到N编号）的街道，每一条街道都是单向的（也就是说你不能逆着该街道指定的方向走），并且在城内无论怎么走都不

27、可能走回原来走过的地方。开始的时候，战士的生命力（HP）为INITHP、站在号路口，而撒旦在第N号路口等待着他。每一条街道上都有许多魔鬼，但是也有一些街道已经被上帝派去的天使占领了。当战士经过连接i号向j号路口的街道时，如果占领该街道的是恶魔，那么他的HP先加倍然后减少Li,j，我们记为Ai,j=-Li,j；如果占领该街道的是天使，那么他的HP就会先加倍然后增加Li,j，我们记为Ai,j=+Li,j；如果该街道不存在，那么Ai,j=0。如果某一时刻战士的HP=0，那么他会死亡。因为这个战士将非常无敌，当他见到撒旦的时候只要还活着，就能一口气把撒旦消灭，所以上帝不希望让他的INITHP过高。任务：给定N，A1.N,1.N，求最小的INITHP，使这个战士能够活着见到撒旦。输入格式：从文件SATANIC.DAT读入数据，文件第一行有一个正整数N（3 N 100），下面跟着的第i行第j个数为Ai,j（绝对值不超过10000的整数）。输出格式：输出所求最小的INITHP。样例SATANIC.DATSATANIC.OUT40 -4 0 100 0 +3 00 0 0 140 0 0 04