2011年軟考程序員考試復(fù)習(xí)筆試知識點(diǎn)整理(13)

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識點(diǎn)整理匯總

　　17、求任意兩個節(jié)點(diǎn)之間最短距離——Floyd算法

　　Floyd算法：給出一個圖(通常可以在任何圖中使用，包括有向圖、帶負(fù)權(quán)邊的圖)，求最短路徑問題的一個O(n^3)算法。

　　優(yōu)點(diǎn)：容易理解，可以算出任意兩個節(jié)點(diǎn)之間最短距離的算法，程序容易寫;

　　缺點(diǎn)：復(fù)雜度達(dá)到三次方，不適合計(jì)算大量數(shù)據(jù);

　　它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。注意單獨(dú)一條邊的路徑也不一定是最佳路徑。

　　Floyd-Warshall算法的基本思路是：

　　1.用d[i][j]記錄每對頂點(diǎn)間的最短距離;

　　2.對每一個圖中的頂點(diǎn)，以其作為基點(diǎn)掃描每一對d[i][j]，檢驗(yàn)是否通過該基點(diǎn)可以使得這對頂點(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í)際是很容易就可以寫出這個算法的代碼：

　　#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];

　　}

　　即使問題是求單源最短路徑，還是推薦使用這個算法，如果時間和空間允許的話(只要有放的下鄰接矩陣的空間，時間上就沒問題)。

　　對上面的代碼來說，我們還面臨一個保存路徑的問題，如何來做呢?

　　/*多源最短路徑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<

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)