高中信息競賽數(shù)據(jù)結(jié)構(gòu)—最短路徑(編輯修改稿)
2025-06-15 10:40 本頁面
【文章內(nèi)容簡介】 其中 dij(n)=min{dij(n1),di,n1(n1)+dn1,j(n1)}。 采用循環(huán)迭代可以簡便求出上述矩陣序列，具體算法如下： D(i,j):dij(k)； Path(i,j)：對應(yīng)于 d(i,j)(k)的路徑上 i的后繼點(diǎn) ,最終的取值為 i到 j的最短路徑上 i的后繼點(diǎn)。 數(shù)據(jù)定義說明： map[][]。//存儲圖 dist[][]。//dis[i,j]=k,i和 j之間最短路徑長度為 K 下面給出 Floyed算法算法框架 : ① 從文件中讀入圖的鄰接矩陣 map； for(i=1。i=n。i++) for(j=1。j=n。j++) cinmap[i][j])。//讀入數(shù)據(jù) ②數(shù)組初始化； for(i=1。i=n。i++) for(j=1。j=n。j++) if(map[i][j]==0)map[i][j]=maxint。 //把沒有通路的點(diǎn) (map[I,j]=0)間的路徑置為最大 maxint Floy算法 — 框架結(jié)構(gòu) 一種算法 ③ Floyed算法框架； void floyd() { int i,j,k。 for(i=1。i=n。i++) //復(fù)抄數(shù)組 for(j=1。j=n。j++) dist[i][j]=map[i][j]。 for(k=1。k=n。k++) //枚舉中間點(diǎn) for(i=1。i=n。i++) //枚舉起點(diǎn) for(j=1。j=n。j++) //枚舉終點(diǎn) if((dist[i][k]!=maxint)amp。amp。(dist[k][j]!=maxint) amp。amp。(dist[i][k]+dist[k][j]dist[i][j])) dist[i][j]=dist[i][k]+dist[k][j]。 } Floy算法 — 框架結(jié)構(gòu) 一種算法 Description：農(nóng)民 John的農(nóng)場里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個(gè)牧場。但是就目前而言，你能看到至少有兩個(gè)牧區(qū)不連通?，F(xiàn)在， John想在農(nóng)場里添加一條路徑 ( 注意，恰好一條 )。對這條路徑有這樣的限制：一個(gè)牧場的直徑就是牧場中最遠(yuǎn)的兩個(gè)牧區(qū)的距離 ( 本題中所提到的所有距離指的都是最短的距離 )?？紤]如下的兩個(gè)牧場，圖１是有 5個(gè)牧區(qū)的牧場，牧區(qū)用“ *”表示，路徑用直線表示。每一個(gè)牧區(qū)都有自己的坐標(biāo)： 圖１所示的牧場的直徑大約是 , 最遠(yuǎn)的兩個(gè)牧區(qū)是 A和 E，它們之間的最短路徑是 ABE。 這兩個(gè)牧場都在 John的農(nóng)場上。 John將會在兩個(gè)牧場中各選一個(gè)牧區(qū)，然后用一條路徑連起來，使得連通后這個(gè)新的更大的牧場有最小的直徑。注意，如果兩條路徑中途相交，我們不認(rèn)為它們是連通的。只有兩條路徑在同一個(gè)牧區(qū)相交，我們才認(rèn)為它們是連通的。 現(xiàn)在請你編程找出一條連接兩個(gè)不同牧場的路徑，使得連上這條路徑后，這個(gè)更大的新牧場有最小的直徑。 例題選講 — 牛的旅行 2092 【 分析 】 ：用 Floyd求出任兩點(diǎn)間的最短路，然后求出每個(gè)點(diǎn)到所有可達(dá)的點(diǎn)的最大距離，記做 mdis[i]。（ Floyd算法） r1=max(mdis[i]) 然后枚舉不連通的兩點(diǎn) i,j，把他們連通，則新的直徑是： mdis[i]+mdis[j]+(i,j)間的距離。 r2=min(mdis[i]+mdis[j]+dis[i,j]) re=max(r1,r2) re就是所求。 例題選講 — 牛的旅行 2092 cinn。 for(i=1。i=n。i++)cinx[i]y[i]。 for(i=1。i=n。i++) for(j=1。j=n。j++) { cinc。 if(c==39。139。)f[i][j]=dist(i,j)。 else f[i][j]=maxint。 } for(k=1。k=n。k++) for(i=1。i=n。i++) for(j=1。j=n。j++) if(f[i][k]maxint1amp。amp。f[k][j]maxint1amp。amp。f[i][j]f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j]。 memset(m,0,sizeof(m))。 for(i=1。i=n。i++) for(j=1。j=n。j++) if(f[i][j]maxint1amp。amp。m[i]f[i][j])m[i]=f[i][j]。 minx=1e20。 for(i=1。i=n。i++) for(j=1。j=n。j++) if(i!=jamp。amp。f[i][j]maxint1) {temp=dist(i,j)。 if(minxm[i]+m[j]+temp)minx=m[i]+m[j]+temp。
法律信息相關(guān)推薦
鄂ICP備17016276號-1