Floyd算法

問題的提出：已知一個有向網(wǎng)(或者無向網(wǎng))，對每一對定點(diǎn)vi!=vj，要求求出vi與vj之間的最短路徑和最短路徑的長度。

解決該問題有以下兩種方法：

(1)輪流以每一個定點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法或者Bellman-Ford算法n次，就可以求出每一對頂點(diǎn)之間的最短路徑和最短路徑的長度，總的時間復(fù)雜度為O(n^3)。

(2)采用Floyd算法，時間復(fù)雜度也是O(n^3)，但是形式更為直接。

1.介紹

floyd算法只有五行代碼，代碼簡單，三個for循環(huán)就可以解決問題，所以它的時間復(fù)雜度為O(n^3)，可以求多源最短路問題。

2.思想：

Floyd算法的基本思想如下：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過若干個節(jié)點(diǎn)X到B。所以，我們假設(shè)Dis(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑的距離，對于每一個節(jié)點(diǎn)X，我們檢查Dis(AX)?+?Dis(XB)?

舉個例子：已知下圖，

如現(xiàn)在只允許經(jīng)過1號頂點(diǎn)，求任意兩點(diǎn)之間的最短路程，只需判斷e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是從i號頂點(diǎn)到j(luò)號頂點(diǎn)之間的路程。e[i][1]+e[1][j]表示的是從i號頂點(diǎn)先到1號頂點(diǎn)，再從1號頂點(diǎn)到j(luò)號頂點(diǎn)的路程之和。其中i是1~n循環(huán)，j也是1~n循環(huán)，代碼實(shí)現(xiàn)如下。

1 for(i=1; i<=n; i++)2 {3 for(j=1; j<=n; j++)4 {5 if ( e[i][j] > e[i][1]+e[1][j] )6 e[i][j] = e[i][1]+e[1][j];7 }8 }

接下來繼續(xù)求在只允許經(jīng)過1和2號兩個頂點(diǎn)的情況下任意兩點(diǎn)之間的最短路程。在只允許經(jīng)過1號頂點(diǎn)時任意兩點(diǎn)的最短路程的結(jié)果下，再判斷如果經(jīng)過2號頂點(diǎn)是否可以使得i號頂點(diǎn)到j(luò)號頂點(diǎn)之間的路程變得更短。即判斷e[i][2]+e[2][j]是否比e[i][j]要小，代碼實(shí)現(xiàn)為如下。

1 //經(jīng)過1號頂點(diǎn)

2 for(i=1; i<=n; i++)3 for(j=1; j<=n; j++)4 if (e[i][j] > e[i][1]+e[1][j])5 e[i][j]=e[i][1]+e[1][j];6 //經(jīng)過2號頂點(diǎn)

7 for(i=1; i<=n; i++)8 for(j=1; j<=n; j++)9 if (e[i][j] > e[i][2]+e[2][j])10 e[i][j]=e[i][2]+e[2][j];

最后允許通過所有頂點(diǎn)作為中轉(zhuǎn)，代碼如下：

1 for(k=1; k<=n; k++)///Floyd-Warshall算法核心語句

2 {3 for(i=1; i<=n; i++)4 {5 for(j=1; j<=n; j++)6 {7 if(map[i][j]>map[i][k]+map[k][j] )8 {9 map[i][j]=map[i][k]+map[k][j];10 }11 }12 }13 }

這段代碼的基本思想就是：最開始只允許經(jīng)過1號頂點(diǎn)進(jìn)行中轉(zhuǎn)，接下來只允許經(jīng)過1和2號頂點(diǎn)進(jìn)行中轉(zhuǎn)……允許經(jīng)過1~n號所有頂點(diǎn)進(jìn)行中轉(zhuǎn)，求任意兩點(diǎn)之間的最短路程。與上面相同

3.代碼模板：

1 #include

2 #define inf 0x3f3f3f3f

3 int map[1000][1000];4 intmain()5 {6 int k,i,j,n,m;///n表示頂點(diǎn)個數(shù)，m表示邊的條數(shù)

7 scanf("%d %d",&n,&m);8 for(i=1; i<=n; i++)///初始化

9 {10 for(j=1; j<=n; j++)11 {12 if(i==j)13 map[i][j]=0;14 else

15 map[i][j]=inf;16 }17 }18 inta,b,c;19 for(i=1; i<=m; i++)///有向圖

20 {21 scanf("%d %d %d",&a,&b,&c);22 map[a][b]=c;23 }24 for(k=1; k<=n; k++)///Floyd-Warshall算法核心語句

25 {26 for(i=1; i<=n; i++)27 {28 for(j=1; j<=n; j++)29 {30 if(map[i][j]>map[i][k]+map[k][j] )31 {32 map[i][j]=map[i][k]+map[k][j];33 }34 }35 }36 }37 for(i=1; i<=n; i++)///輸出最終的結(jié)果,最終二維數(shù)組中存的即使兩點(diǎn)之間的最短距離

38 {39 for(j=1; j<=n; j++)40 {41 printf("%10d",map[i][j]);42 }43 printf("\n");44 }45 return 0;46 }

總結(jié)

以上是生活随笔為你收集整理的任意两点最短路floyd算法matlab,多源最短路——Floyd算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。