更多:2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理匯總
17、求任意兩個(gè)節(jié)點(diǎn)之間最短距離——Floyd算法
Floyd算法:給出一個(gè)圖(通?梢栽谌魏螆D中使用,包括有向圖、帶負(fù)權(quán)邊的圖),求最短路徑問題的一個(gè)O(n^3)算法。
優(yōu)點(diǎn):容易理解,可以算出任意兩個(gè)節(jié)點(diǎn)之間最短距離的算法,程序容易寫;
缺點(diǎn):復(fù)雜度達(dá)到三次方,不適合計(jì)算大量數(shù)據(jù);
它需要用鄰接矩陣來儲(chǔ)存邊,這個(gè)算法通過考慮最佳子路徑來得到最佳路徑。注意單獨(dú)一條邊的路徑也不一定是最佳路徑。
Floyd-Warshall算法的基本思路是:
1.用d[i][j]記錄每對(duì)頂點(diǎn)間的最短距離;
2.對(duì)每一個(gè)圖中的頂點(diǎn),以其作為基點(diǎn)掃描每一對(duì)d[i][j],檢驗(yàn)是否通過該基點(diǎn)可以使得這對(duì)頂點(diǎn)間的距離變小。
//dist(i,j) 為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離
Fori←1 to n do
For j←1 to n do
dist(i,j) = weight(i,j)
Fork←1 to n do // k為“媒介節(jié)點(diǎn)”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j))then // 是否是更短的路徑?
dist(i,j) = dist(i,k) + dist(k,j)
我們實(shí)際是很容易就可以寫出這個(gè)算法的代碼:
#defineN 100
voidFloyd(int dist[N][N],int n)
{
int i,j,k;
for(k=0;k for(i=0;i for(j=0;j if(dist[i][k]+dist[k][j] dist[i][j]=dist[i][k]+dist[k][j]; } 即使問題是求單源最短路徑,還是推薦使用這個(gè)算法,如果時(shí)間和空間允許的話(只要有放的下鄰接矩陣的空間,時(shí)間上就沒問題)。 對(duì)上面的代碼來說,我們還面臨一個(gè)保存路徑的問題,如何來做呢? /*多源最短路徑floyd_warshall算法*/ #defineN 100 intmap[N][N]; voidFloyd(int dist[N][N],int path[N][N],int n) { int i,j,k; for(i=0;i for(j=0;j dist[i][j]=map[i][j], path[i][j]=0; for(k=0;k for(i=0;i for(j=0;j if(dist[i][k]+dist[k][j] { dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=k; } } voidoutput(int i,int j) { if(i==j) return; if(path[i][j]==0) cout<
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |