最短路径与标号法

《最短路径与标号法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、jkstra算法）算法思想：设源点为x0，dist[i]表示顶点i到源点x0的最短路径长度，map[i,j]表示图中顶点i到顶点j的长度，用数组mark对所有的顶点作标记，已求出源点到达该点J的最短路径的点J记为mark[j]=true,否则标记为false。初始时，对源点作标记，然后从未作标记的点中找出到源点路径长度最短的顶点minj，对该顶点作标记，并对其它未作标记的点K作判断：ifdist[minj]+map[minj,k]

3、程：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

4、[j])and(dist[j]0)thenbegintemp:=dist[minj]+map[minj,j];iftemp

5、出某市各镇间路线网络图，市汽车站在市区A，现要求出市汽车站到各镇区的最短路径长度。B8E121510914A301015F1113DC数据输入：从文件city.dat中读入数据，第一行为镇区个数N，以下有N行，每行N个数据，在数据阵中，第i行第j列的数表示城镇i到城镇j的距离。最后一行为市区中心所在位置的编号。数据输出结果输出到文件city.out中，共有N-1行，每行由市区到达的镇区号、最短路径长度。输入输出样例city.dat60121130001209148151190130030141301015080100100150151001city.out212311424520639分析：

6、本题是典型的求单源最短路径问题，本直接用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);rea

7、dln(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]:=