最短路径与标号法

最短路径与标号法前面我们学习过动态规划的应用，图中没明显阶段求最短路径的问题属于无明显阶段的动态规划，通常用标号法求解，求最短路径问题是信息学奥赛中很重要的一类问题，许多问题都可转化为求图的最短路径来来解，图的最短路径在图论中有经典的算法，本章介绍求图的最短路径的dijkstra算法、Floyed算法，以及标号法。一、最短路径的算法1、单源点最短路径（dijkstra算法）给定一个带权有向图G=（V，E），其中每条边的权是一个非负实数，另外，还给定V中的一个顶点，称为源点。求从源点到所有其他各顶点的最短路径长度。这个问题称为单源最短路径问题。求单源最短路径可用dijkstra算法求解。（dijkstra算法）算法思想：设源点为x0，dist[i]表示顶点i到源点x0的最短路径长度，map[i,j]表示图中顶点i到顶点j的长度，用数组mark对所有的顶点作标记，已求出源点到达该点J的最短路径的点J记为mark[j]=true,否则标记为false。初始时，对源点作标记，然后从未作标记的点中找出到源点路径长度最短的顶点minj，对该顶点作标记，并对其它未作标记的点K作判断：ifdist[minj]+map[minj,k]<dist[k]thendist[k]=dist[minj]+map[minj,k]。重复处理，直到所有的顶点都已作标记，这时求出了源点到所有顶点的最短路径。算法过程：constmaxn=100;varmap:array[1..maxn,1..maxn]ofinteger;dist:array[1..maxn]ofinteger;mark:array[1..maxn]ofBoolean;n,k:integer;proceduredijkstra;varI,j,min,minj,temp:integer;beginfillchar(mark,sizeof(mark),0);forI:=1tondodist[i]:=maxint;dist[k]:=0;forI:=1ton-1dobeginmin:=maxint;forj:=1tondoif(notmark[j])and(dist[j]<min)thenbeginmin:=dist[j];minj:=j;end;mark[minj]:=true;forj:=1tondoif(notmar[j])and(map[minj,j]>0)thenbegintemp:=dist[minj]+map[minj,j];iftemp<dist[j]thendist[j]:=temp;end;end;end;以上只是求出了从源点到其它所有点的最短路径长度，所经过的具体路径没有保存，如果要求出具体的路径来，那么在求最短路径的过程中要将经过的中间点记录下来。下面通过例题来说明最短路径的求解。例1：最短路径问题下面给出某市各镇间路线网络图，市汽车站在市区A，现要求出市汽车站到各镇区的最短路径长度。B8E121510914A301015F1113DC数据输入：从文件city.dat中读入数据，第一行为镇区个数N，以下有N行，每行N个数据，在数据阵中，第i行第j列的数表示城镇i到城镇j的距离。最后一行为市区中心所在位置的编号。数据输出结果输出到文件city.out中，共有N-1行，每行由市区到达的镇区号、最短路径长度。输入输出样例city.dat60121130001209148151190130030141301015080100100150151001city.out212311424520639分析：本题是典型的求单源最短路径问题，本直接用dijkstra算法求解。程序如下：programcity;constmaxn=100;varmap:array[1..maxn,1..maxn]ofinteger;dist:array[1..maxn]ofinteger;mark:array[1..maxn]ofBoolean;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);fori:=1tondobeginforj:=1tondobeginread(fin,map[i,j]);ifmap[i,j]=0thenmap[i,j]:=maxint;end;readln(fin);end;readln(fin,first);close(fin);fillchar(mark,sizeof(mark),0);k:=first;forI:=1tondodist[i]:=map[k,i];dist[k]:=0;mark[k]:=true;forI:=1ton-1dobeginmin:=maxint;forj:=1tondoif(notmark[j])and(dist[j]<min)thenbeginmin:=dist[j];minj:=j;end;mark[minj]:=true;forj:=1tondoif(notmar[j])and(map[minj,j]>0)thenbegintemp:=dist[minj]+map[minj,j];iftemp<dist[j]thendist[j]:=temp;end;end;fori:=1tondoifi<>firstthenwriteln(fout,i,’‘,dist[i]);close(fout);end;2、所有顶点对之间的最短路径Floyed算法设图G=（V，E），顶点I到顶点J的权为cost[I,j],顶点I到顶点J的最短路径长度为A[I，J]，路径为P[I，J]。Floyed算法算法思想：从任意顶点VI到VJ的路径上，每次增加一个顶点VK（K=1，2，…,N），然后，比较增加VK后的路径是否比原来的路径短，取其中短者作为从VI到ＶＪ的当前最短路径。当Ｋ从取值１到取值Ｎ，经过Ｎ次这样的比较后，最终求得的就是任意两顶点ＶＩ和ＶＪ间的最短路径。算法过程：constn=50;typepathdata=array[1..n,1..n]of0..n;mapdata=array[1..n,1..n]ofinteger;varp:pathdata;a:mapdata;procedurepath(varp:pathdata;I,j:integer);vark:integer;begink:=p[I,j];ifk<>0thenbeginpath(p,I,k);writeln(k);path(p,k,j);end;end;procedurefloyed(vara,cost:mapdata;varp:pathdata);varI,j,k:integerbeginforI:=1tondoforj:=1tondobegina[I,j]:=cost[I,j];path[I,j]:=0;end;fork:=1tondoforI:=1tondoforj:=1tondoifa[I,k]+a[k,j]<a[I,j]thenbegina[I,j]:=a[I,k]+a[k,j];p[I,j]:=k;end;end;注意：dijkstra算法要求网中的权值都非负，否则，算法虽可执行，但结果有误。而floyed算法则允许网中边上的权值为负，但不允许网中出现路径长度为负的回路。例2、哈利波特与魔法石石子路草地23石子路草地2341石子路森林大年初三的那个晚上，小可可去电影院看了《哈利波特与魔法石》，回到家坐在椅子上不一会儿就睡着了，并且梦见自己成了哈利波特驰骋在充满了正义与邪恶的宇宙中执著地为了正义而战。那天哈利波特去拯救Supersamuel星球上的生灵，该星球上有七种不同的地形，依次分别是石子路、森林、草地、山地、雪地、沼泽和沙漠，用数字1-7表示，任意两个城市之间都存在至少一条通路，而且任意两个不经过别的城市而直接通达的城市I和J之间都只存在一种地形T（I，J），奇怪的地，在Supersamuel星球上哈利波特穿越地形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，S（3）＝S（4）＝S（5）＝S（6）＝S（7）＝0，即只有森林中有魔法石，因此穿越森林所花费的时间是6/2=3，穿越石子路和草地的时间仍然分别是2和4。如果哈利波特想从城市1到城市4，则最快的路线是经过城市2，这条路线需要的时间是2＋3＝5。哈利波特总是忙于铲除邪恶、伸张正义，没有时间去寻找从起点城市I到终点城市J之间的最快路线。现在聘你作为哈利波特的助手编写程序寻找最快路线为哈利波特腾出更多的时间来将正义事业进行到底。数据输入：数据从文件halibote.dat读入，文件中第一行有七个数，分别是S（1）至S（7）；第二行有两个数，依次分别是起点城市I和终点城市J；第三行有一个正整数C，C<=10000，表示随后的C行中每行存放了一对能直接通达的城市的信息，能直接通达的城市的信息由三个数组成，依次分别是两个城市的编号和这两个城市之间的地形。城市的编号都是不超过100的正整数，但是各个城市的编号未必连续。文件里同一行中查邻的两个数都是用一个空白字符隔开的。数据输出：结果输出到文件halibote.out中，以一行的形式输出起点城市I与终点城市J之间的最快路线所需要的时间。输入输出样例：halibote.dat0100000144121131242343halibote.out5分析：本题也是很明显的求最短路径问题，根据题目给出的数据和条件，先构造出网络图，然后用最短路径的floyed算法求解。程序如下：programhalibote;consthh:array[1..7]ofinteger=(2,6,4,8,6,10,14);varf:text;map:array[1..100,1..100]oflongint;s:array[1..7]of0..1;x,y,ma:longint;se:setof1..100;procedurereadin;vari,j,k,l,c:longint;beginassign(f,'halibote.dat');reset(f);fori:=1to100doforj:=1to100doifi=jthenmap[i,j]:=0elsemap[i,j]:=0;ma:=0;fori:=1to7doread(f,s[i]);readln(f,x,y);readln(f,c);fori:=1tocdobeginread(f,j,k,l);map[j,k]:=hh[l]div(s[l]+1);map[k,j]:=map[j,k];ifj>mathenma:=j;ifk>mathenma:=k;se:=se+[j]+[k];end;close(f);end;proceduremain;vari,j,k:integer;beginfori:=1tomadoforj:=1tomadoif(iinse)and(i<>j)and(jinse)thenbeginfork:=1tomadoif(k<>i)and(k<>j)and(map[i,k]>0)and(map[k,j]>0)and(map[i,k]+map[k,j]<map[i,j])thenbeginmap[i,j]:=map[i,k]+map[k,j];map[j,i]:=map[i,j];end;end;end;procedureprint;beginassign(f,'halibote.out');rewrite(f);writeln(f,map[x,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）队列初始化，Vs进入队列L，X[1]:=s,sum[1]=0；（2）取队首结点VK，若VK是目标结点Ve，则输入结果（最短路径值及路径），程序结束；否则继续（3）；（3）由VK扩展出结点VJ（结点VK与VJ相连），计算代价值若Sum(k)+map[k,j]<sum(j)则替换结点J的代价，换代价值由小到大插入队列，并记录其父结点：sum(j):=sum(k)+map[k,j],fa[j]:=k，结点J入队列继续（2），否则直接转（2）。注意：1.只有两个顶点间的距离为非负时，才可用标号法。2.只有队列的首结点是目标结点时，才可停止计算。否则得出的不一定是最优解。标号法算法伪代码如下：fillchar(x,sizeof(x),0);forI:=1tondobeginsum[I]:=map[s,I];fa[I]:=s;end;x[1]:=s;sum[s]:=0;open:=1;close:=1;fa[s]:=0;repeattemp:=x[open];iftemp=Vethenprint{调用输出结果过程};halt;forj:=1tondoif(sum[temp]+map[temp,j]<sum[j])and(map[temp,j]>0)thenbeginsum[j]:=sum[temp]+map[temp,j];close:=close+1;按代价由小到大将结点J插入队列；fa[j]:=open;end;open:=open+1;untilopen>close例3：Car的旅行路线问题描述又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。图例

机场

高速铁路

飞机航线

注意：图中并没有

标出所有的铁路与航线。那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。

任务

找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

输入文件：键盘输入文件名

输出：到屏幕(输出最小费用，小数点后保留2位。)

输入格式

第一行为一个正整数n(0<=n<=10)，表示有n组测试数据。

每组的第一行有四个正整数s，t，A，B。

S(0<S<=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1<=A，B<=S)。

接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，Ti为第I个城市高速铁路单位里程的价格。

输出格式

共有n行，每行一个数据对应测试数据。样例

输入

1

31013

11133130

2574521

86881163

输出：

47.55分析：本题是简单的几何计算和最短路径相结合的问题，首先对于每个城市根据给出的三个机场的坐标计算出第四个机场的坐标，以城市A的四个机场分别作为起始结点，以城市B的四个机场分别作为目标结点，用标号法计算出所有最小代值值，从中找出最小代价即为问题的解。程序如下：ProgramCar;ConstReadFile='input.dat';TypeAirport_Type=Recordx,y:longintend;Line_Type=RecordFather,Son,Airport:integer;Value:real;end;varn,s,A,B,Head,Tail,c,d,e:integer;t:longint;Airport:array[1..400]ofAirport_Type;Line:array[1..400]ofLine_Type;Railway:array[1..100]oflongint;RF:text;functionGet_Length(P11,P12:integer):real;varA1,A2:longint;beginA1:=sqr(Airport[P11].x-Airport[P12].x);A2:=sqr(Airport[P11].y-Airport[P12].y);Get_Length:=sqrt(A1+A2);end;procedureMain;vari,j:integer;Fintout:boolean;Tmp_Value:real;beginFintout:=False;repeatinc(Head);if(Line[Head].Airportdiv4)+1=Bthenbeginwriteln(Line[Head].Value:0:2);Fintout:=True;endelsebeginforj:=1to4*sdobeginTmp_Value:=Line[Head].Value;if(Line[Head].Airportdiv4)=(jdiv4)thenbeginTmp_Value:=Tmp_Value+Railway[(Line[Head].Airportdiv4)+1]*Get_Length(Line[Head].Airport,j);endelsebeginTmp_Value:=Tmp_Value+t*Get_Length(Line[Head].Airport,j);end;i:=1;WhileNot((Line[i].Airport=j)or(Line[i].Son=0))dobegini:=Line[i].Sonend;ifLine[i].Son=0thenbegininc(Tail);Line[Tail].Value:=Tmp_Value;i:=Head;repeati:=Line[i].Son;until((Line[i].Value>Tmp_Value)or(Line[i].Son=0));ifLine[i].Son=0thenbeginLine[i].Son:=Tail;Line[Tail].Father:=i;Line[Tail].Son:=0;endelsebeginLine[Tail].Fahter:=Line[i].Father;Line[Tail].Son:=i;Line[i].Father:=Tail;end;endelsebeginend;end;end;untilFintout;end;procedureMade_The_4th_Point;vari,j,P1,P2,P3:integer;Max:real;beginMax:=0;fori:=(d-1)*4+1to(d-1)*4+2doforj:=i+1to(d-1)*4+3doifGet_Length(i,j)>MaxthenbeginMax:=Get_Length(i,j);P1:=i;P2:=j;end;P3:=(d-1)*4*3+6-P1-P2;Airport[d*4].x:=Airport[P1].x+Airport[P2].x-Airport[p3].x;Airport[d*4].y:=Airport[P1].y+Airport[P2].y-Airport[p3].y;end;beginassign(RF,ReadFile);reset(RF);readln(RF,n);forc:=1tondobeginreadln(RF,s,t,A,B);ford:=1tosdobeginfore:=1to3doread(RF,Airport[(d-1)*4+e].x,Airport[(d-1)*4+e].y);Made_The_4th_Point;read(RF,Railway[c]);end;Head:=0;Tail:=4;ford:=1to4dobeginLine[d].Father:=0;Line[d].Son:=d+1;Line[d].Airport:=A*4-4+d;Line[d].Value:=0;end;Line[4].Son:=0;Main;end;close(RF);end.三、练习1、最佳路线问题描述

塞内加尔是非洲的一个小国家，你也许很难在世界地图上找到它，甚至你有可能从未听说过它--它实在是个太小、太贫穷的国家了。可是，就是这个人口不足900万、全国仅有2个标准足球场地的小国，在2002韩日世界杯的非洲区预选赛中脱颖而出，取得了世界杯决赛圈的入场券（幸好，去年中国队也进入了世界杯决赛圈，不然可就丢脸了）。

在塞内加尔全国球迷欣喜若狂，世界足球行家大跌眼镜的同时，塞内加尔足协却发现自己面临着一个颇为尴尬的问题--说起来令人不可思议，由于打非洲区预选赛时四处征战，加上足协经营不力，现在足协的预算以几近赤字--也就是说，塞内加尔足协支付不起从本国乘飞机到达韩国参加世界杯的费用！经过三思，塞内加尔足协向非洲足联递交了一份《关于减免球队旅行费用》的申请；可是--众所周知的，非洲足联也是惨淡经营，幸好非洲足联秘书长神通广大，弄来了M张优惠乘机券：每张优惠券可以作用于一条航线，使全队通过此航线的费用减半；多张优惠券用于同一条线路，其效果叠加--即在一条航线上用两张优惠券，其费用降为原费用的1/4，依此类推。

【问题】

塞内加尔足球队要从塞内加尔国家机场出发，途经一些中转机场，最后要到达韩国釜山机场。为了合理地分配各张优惠券，使得所需费用最少，塞内加尔足协找到了你，请你编程解决这个问题。

【输入】

第1行有两个数N、M（0<N<=70，0<=M<=20）并用空格隔开，分别表示包括起点（塞内加尔国家机场）、终点（韩国釜山机场）的机场数，以及塞内加尔足协现有的优惠券数量。

从第2行到第N+1行起，每行有N个数，其中第I行的第J个数代表从机场I到机场J所需费用；为零的数代表两机场无航线。

假设起点标号为1，终点标号为N。

【输出】

第1行仅有一个数（保留两位小数），代表所求得的从机场1到机场N的最小费用；

第2行打印航线，每两个机场间用"->"连接（参见样例输出）；

输入数据保证从塞内加尔机场可达釜山机场。

【样例输入】