文档介绍：最短路径与标号法前面我们学****过动态规划的应用,图中没明显阶段求最短路径的问题属于无明显阶段的动态规划,通常用标号法求解,求最短路径问题是信息学奥赛中很重要的一类问题, 许多问题都可转化为求图的最短路径来来解,图的最短路径在图论中有经典的算法,本章介绍求图的最短路径的 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] then dist[k]= dist[minj]+map[minj,k] 。重复处理,直到所有的顶点都已作标记,这时求出了源点到所有顶点的最短路径。算法过程: const maxn=100; var map: array[1..maxn,1..maxn] ofinteger; dist: array[1..maxn] ofinteger; mark: array[1..maxn] ofBoolean; n,k: integer; procedure dijkstra; var I,j,min,minj,temp:integer; begin fillchar(mark,sizeof(mark),0); for I:=1 tondodist[i]:=maxint; dist[k]:=0; for I:=1 ton-1 do begin min:=maxint; for j:=1 tondo if(not mark[j]) and (dist[j]<min) then begin min:=dist[j]; minj:=j; end; mark[minj]:=true; for j:=1 tondo if(not mar[j]) and (map[minj,j]>0) then begin temp:=dist[minj]+map[minj,j]; iftemp<dist[j] then dist[j]:=temp; end; end; end; 以上只是求出了从源点到其它所有点的最短路径长度,所经过的具体路径没有保存,如果要求出具体的路径来,那么在求最短路径的过程中要将经过的中间点记录下来。下面通过例题来说明最短路径的求解。例1:最短路径问题下面给出某市各镇间路线网络图,市汽车站在市区 A ,现要求出市汽车站到各镇区的最短路径长度。数据输入: 从文件 中读入数据,第一行为镇区个数 N,以下有 N行,每行 N个数据, 在数据阵中,第 i行第 j列的数表示城镇 i到城镇 j的距离。最后一行为市区中心所在位置的编号。数据输出 B8E 12 15 10 9 14 A 30 10 15F 11 13D C 结果输出到文件 中,共有 N-1 行,每行由市区到达的镇区号、最短路径长度。输入输出样例 6012113000120914815 1190130030141301015 08010010 212 311 424 520 639 分析: 本题是典型的求单源最短路径问题,本直接用 dijkstra 算法求解。程序如下: program city; const maxn=100; var map: 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; begin assign(fin, ’ ’); assign(fout, ’ ’); reset(fin); rewrite(fout); readln(fin,n); for i:=1 tondo beg