[考试]最短路径与标号法.doc

[考试]最短路径与标号法最短路径与标号法前面我们学****过动态规划的应用,图中没明显阶段求最短路径的问题属于无明显阶段的动态规划,通常用标号法求解,求最短路径问题是信息学奥赛中很重要的一类问题,许多问题都可转化为求图的最短路径来来解,图的最短路径在图论中有经典的算法,本章介绍求图的最短路径的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数据输入:,第一行为镇区个数N,以下有N行,每行N个数据,在数据阵中,第i行第j列的数表示城镇i到城镇j的距离。最后一行为市区中心所在位置的编号。,共有N-1行,每行由市区到达的镇区号、最短路径长度。**********分析:本题是典型的求单源最短路径问题,本直接用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,’’);assign(fout,’’);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:=1to