安陽(yáng)一中-月26日最短路徑

（Floyd）算法求Vi到Vj的最短路徑如果cost[i,j]<>max,從Vi到Vj存在一條長(zhǎng)度為cost[i,j]的路徑，但該路徑不一定是最短路徑，尚需進(jìn)行n次試探。設(shè)具有n個(gè)頂點(diǎn)的一個(gè)帶權(quán)圖G的鄰接矩陣用GA表示，再設(shè)一個(gè)與GA同類型的表示每對(duì)頂點(diǎn)之間的最短路徑長(zhǎng)度的二維數(shù)組A，A的初值等于GA。Floyed算法需要在A上進(jìn)行n次運(yùn)算，每次以vk（1≤k≤n）作為新考慮的中間點(diǎn)，求出每對(duì)頂點(diǎn)之間的當(dāng)前最短路徑長(zhǎng)度，最后依次運(yùn)算后，A中的每個(gè)元素A[i，j]就是圖G中從頂點(diǎn)vi到vj的最短路徑長(zhǎng)度。再設(shè)一個(gè)二維數(shù)組P[1..n，1..n]，記錄最短路徑，其元素類型為集合類型set

of

1..n。2、任意一對(duì)頂點(diǎn)之間的最短路徑（FLOYED）；首先，考慮路徑（Vi,V1,Vj）是否存在（即判別?。╒i,V1）和（V1，Vj）是否存在）。如果存在，則比較（Vi,Vj）與（Vi,V1,Vj）的路徑長(zhǎng)度較短者為從Vi到Vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑。在路徑上再增加一個(gè)頂點(diǎn)V2，也就是說(shuō)，如果（Vi,…,V2)和（V2,…,Vj)分別是當(dāng)前找到的中間頂點(diǎn)不大于1的最短路徑，那么（

Vi,…,V2,…,Vj)就有可能是Vi到Vj的中間頂點(diǎn)的序號(hào)不大于2的最短路徑。將它和中間頂點(diǎn)不大于1的最短路徑

相比較，從中選出中間頂點(diǎn)不大于2的最短路徑。再增加頂點(diǎn)V3，繼續(xù)進(jìn)行試探，依此類推，直到經(jīng)過(guò)n次比較后，最后求得Vi到Vj的中間頂點(diǎn)的序號(hào)不大于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;{無(wú)需計(jì)算，直接進(jìn)入下一輪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;{最短路徑長(zhǎng)度數(shù)組和最短路徑數(shù)組初始化}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個(gè)點(diǎn)（n<=100)每個(gè)點(diǎn)的坐標(biāo)均在-10000~10000之間.其中的一些點(diǎn)之間有連線。若有連線，則表示可以從一個(gè)點(diǎn)到達(dá)另一個(gè)點(diǎn)，即兩點(diǎn)間有通路，通路的距離為兩點(diǎn)間的直線距離?，F(xiàn)在的任務(wù)是找出從一點(diǎn)到另一點(diǎn)之間的最短路徑。輸入：輸入文件為short.in，共n+m+3行，其中：第一行為整數(shù)n。第二行到n+1行（共n行），每行兩個(gè)整數(shù)x和y，描述了一個(gè)點(diǎn)的坐標(biāo)（以一個(gè)空格分隔）。第n+2行為一個(gè)整數(shù)m，表示圖中連線的個(gè)數(shù)。此后的m行，每行描述一條連線，由兩個(gè)整數(shù)I和j組成，表示第I個(gè)點(diǎn)和j個(gè)點(diǎn)之間有連線。最后一行：兩個(gè)整數(shù)s和t，分別表示與源點(diǎn)和目標(biāo)點(diǎn)。輸出：輸出文件為short.out，僅一行，一個(gè)實(shí)數(shù)（保留兩位小數(shù)），表示從s到t的最短路徑長(zhǎng)度。樣例輸入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算法的思想可用于判斷有向圖中任意兩點(diǎn)是否連通？算法如下：For

k:=

1

to