安阳一中-月26日最短路径

（Floyd）算法求Vi到Vj的最短路径如果cost[i,j]<>max,从Vi到Vj存在一条长度为cost[i,j]的路径，但该路径不一定是最短路径，尚需进行n次试探。设具有n个顶点的一个带权图G的邻接矩阵用GA表示，再设一个与GA同类型的表示每对顶点之间的最短路径长度的二维数组A，A的初值等于GA。Floyed算法需要在A上进行n次运算，每次以vk（1≤k≤n）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，最后依次运算后，A中的每个元素A[i，j]就是图G中从顶点vi到vj的最短路径长度。再设一个二维数组P[1..n，1..n]，记录最短路径，其元素类型为集合类型set

of

1..n。2、任意一对顶点之间的最短路径（FLOYED）；首先，考虑路径（Vi,V1,Vj）是否存在（即判别弧（Vi,V1）和（V1，Vj）是否存在）。如果存在，则比较（Vi,Vj）与（Vi,V1,Vj）的路径长度较短者为从Vi到Vj的中间顶点的序号不大于1的最短路径。在路径上再增加一个顶点V2，也就是说，如果（Vi,…,V2)和（V2,…,Vj)分别是当前找到的中间顶点不大于1的最短路径，那么（

Vi,…,V2,…,Vj)就有可能是Vi到Vj的中间顶点的序号不大于2的最短路径。将它和中间顶点不大于1的最短路径

相比较，从中选出中间顶点不大于2的最短路径。再增加顶点V3，继续进行试探，依此类推，直到经过n次比较后，最后求得Vi到Vj的中间顶点的序号不大于n的最短路径。Procedure

floyed(GA,A,P);beginfor

I:=

1

to

n

doforj:=1

to

ndobeginA[I,j]:=GA[I,j];if

A[I,j]<

maxint

thenp[I,j]:=[I]+[j]elsep[I,j]:=[

];End;fork:=

1to

nd0for

I:=1

to

n

doforj:=

1tondobeginif

(I=k)or

(j=k)or

(I=j)

then

continue;{无需计算，直接进入下一轮if

A[I,k]+A[k,j]<A[I,J]

then

begin

{找到更短路径保存}A[I,J]:=A[I,K]+A[K,J];P[I,J]:=P[I,K]+P[K,J];END;END;END;{最短路径长度数组和最短路径数组初始化}fork:=1

tondofori:=1

tondoforj:=1

tondoif

leng[i,k]+leng[k,j]<leng[i,j]

thenbegin

leng[i,j]:=leng[i,k]+leng[k,j];path[i,j]:=path[i,k]+copy(path[k,j],2,length(path[k,j])-1);end;例1、平面上有n个点（n<=100)每个点的坐标均在-10000~10000之间.其中的一些点之间有连线。若有连线，则表示可以从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。输入：输入文件为short.in，共n+m+3行，其中：第一行为整数n。第二行到n+1行（共n行），每行两个整数x和y，描述了一个点的坐标（以一个空格分隔）。第n+2行为一个整数m，表示图中连线的个数。此后的m行，每行描述一条连线，由两个整数I和j组成，表示第I个点和j个点之间有连线。最后一行：两个整数s和t，分别表示与源点和目标点。输出：输出文件为short.out，仅一行，一个实数（保留两位小数），表示从s到t的最短路径长度。样例输入5002022023515样例输出3.41program

t1(input,output);typepoint=recordx,y:integer;end;var

g:array[1..100,1..100]

ofreal;pos:array[1..100]

ofpoint;n,m,x,y,i,j,k,s,t:integer;

function

dist(i,j:integer):real;begindist:=sqrt(sqr(pos[i].x-pos[j].x)+sqr(pos[i].y-pos[j].y))end;beginassign(input,'short.in');reset(input);assign(output,'short.out')rewrite(output);readln(n);for

i:=

1ton

doreadln(pos[i].x,pos[i].y);for

i:=

1ton

dofor

j:=1

tondog[i,j]:=1e30;readln(m);for

i:=1

to

m

dobeginreadln(x,y);g[x,y]:=dist(x,y);g[y,x]:=g[x,y]end;readln(s,t);for

k:=1

ton

dofori:=1tondoif

i<>k

thenfor

j:=1

ton

doif

(i<>j)and(k<>j)and(g[i,k]<g[i,j])theng[i,j]:=g[i,k]+g[k,j];wri

n(g[s,t]:0:2);close(input);close(output);end.Floyed算法的思想可用于判断有向图中任意两点是否连通？算法如下：For

k:=

1

to