個人筆記，僅供復習

1.適用范圍：求每一對頂點之前的最短路徑（適用稠密圖）

2.算法思想：在一般情況下，若（vi，…，vk ）和（ vk，…，vj ）分別是從 vi 到 vk 和從 vk 到 vj 的 中間頂點的序號不大于k的最短路徑，則將（ vi，…， vk ，… ， vj ）和已經(jīng)得到的從vi到vj且中間頂點的序號不大于k-1的最短路徑相比較，其長度較短者便是從vi到vj的中間頂點的序號不大于k的最短路徑。這樣，在經(jīng)過n次比較后，最后求得的必是從vi到vj的最短路徑。按此方法，可以同時求得各對頂點間的最短路徑。

3.具體步奏：其中D(k)[i][j]，表示只經(jīng)過頂點編號小于k的頂點i與j的最短路徑。

4.代碼參考：

void Floyd() { for ( i = 0; i < N; i++ )for( j = 0; j < N; j++ ) {D[i][j] = G[i][j];path[i][j] = -1;}for( k = 0; k < N; k++ )for( i = 0; i < N; i++ )for( j = 0; j < N; j++ )if( D[i][k] + D[k][j] < D[i][j] ) {D[i][j] = D[i][k] + D[k][j];path[i][j] = k;} }

轉載于:https://www.cnblogs.com/long98/p/10352228.html

總結

以上是生活随笔為你收集整理的Floyd算法 笔记 C/C++的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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