正如我們所知道的，Floyd算法用于求最短路徑。Floyd算法可以說是Warshall算法的擴展，三個for循環就可以解決問題，所以它的時間復雜度為O(n^3)。

Floyd算法的基本思想如下：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點X到B。所以，我們假設Dis(AB)為節點A到節點B的最短路徑的距離，對于每一個節點X，我們檢查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設置Dis(AB) = Dis(AX) + Dis(XB)，這樣一來，當我們遍歷完所有節點X，Dis(AB)中記錄的便是A到B的最短路徑的距離。

很簡單吧，代碼看起來可能像下面這樣：

for?( int?i = 0; i < 節點個數; ++i ){for?( int?j = 0; j < 節點個數; ++j ){for?( int?k = 0; k < 節點個數; ++k ){if?( Dis[i][k] + Dis[k][j] < Dis[i][j] ){// 找到更短路徑Dis[i][j] = Dis[i][k] + Dis[k][j];}}}}

但是這里我們要注意循環的嵌套順序，如果把檢查所有節點X放在最內層，那么結果將是不正確的，為什么呢？因為這樣便過早的把i到j的最短路徑確定下來了，而當后面存在更短的路徑時，已經不再會更新了。

讓我們來看一個例子，看下圖：

圖中紅色的數字代表邊的權重。如果我們在最內層檢查所有節點X，那么對于A->B，我們只能發現一條路徑，就是A->B，路徑距離為9。而這顯然是不正確的，真實的最短路徑是A->D->C->B，路徑距離為6。造成錯誤的原因就是我們把檢查所有節點X放在最內層，造成過早的把A到B的最短路徑確定下來了，當確定A->B的最短路徑時Dis(AC)尚未被計算。所以，我們需要改寫循環順序，如下：

for?( int?k = 0; k < 節點個數; ++k ){for?( int?i = 0; i < 節點個數; ++i ){for?( int?j = 0; j < 節點個數; ++j ){if?( Dis[i][k] + Dis[k][j] < Dis[i][j] ){// 找到更短路徑Dis[i][j] = Dis[i][k] + Dis[k][j];}}}}

這樣一來，對于每一個節點X，我們都會把所有的i到j處理完畢后才繼續檢查下一個節點。

那么接下來的問題就是，我們如何找出最短路徑呢？這里需要借助一個輔助數組Path，它是這樣使用的：Path(AB)的值如果為P，則表示A節點到B節點的最短路徑是A->...->P->B。這樣一來，假設我們要找A->B的最短路徑，那么就依次查找，假設Path(AB)的值為P，那么接著查找Path(AP)，假設Path(AP)的值為L，那么接著查找Path(AL)，假設Path(AL)的值為A，則查找結束，最短路徑為A->L->P->B。

那么，如何填充Path的值呢？很簡單，當我們發現Dis(AX) + Dis(XB) < Dis(AB)成立時，就要把最短路徑改為A->...->X->...->B，而此時，Path(XB)的值是已知的，所以，Path(AB) = Path(XB)。

好了，基本的介紹完成了，接下來就是實現的時候了，這里我們使用圖以及鄰接矩陣：

#define INFINITE 1000?????????? // 最大值#define MAX_VERTEX_COUNT 20 　　// 最大頂點個數//struct?Graph{int?????arrArcs[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];??? // 鄰接矩陣int?????nVertexCount;?????????????????????????????? 　　// 頂點數量int?????nArcCount;????????????????????????????????? 　　// 邊的數量};//

首先，我們寫一個方法，用于讀入圖的數據：

void?readGraphData( Graph *_pGraph ){std::cout << "請輸入頂點數量和邊的數量: ";std::cin >> _pGraph->nVertexCount;std::cin >> _pGraph->nArcCount;std::cout << "請輸入鄰接矩陣數據:"?<< std::endl;for?( int?row = 0; row < _pGraph->nVertexCount; ++row ){for?( int?col = 0; col < _pGraph->nVertexCount; ++col ){std::cin >> _pGraph->arrArcs[row][col];}}}

接著，就是核心的Floyd算法：

void?floyd( int?_arrDis[][MAX_VERTEX_COUNT], int?_arrPath[][MAX_VERTEX_COUNT], int?_nVertexCount ){// 先初始化_arrPathfor?( int?i = 0; i < _nVertexCount; ++i ){for?( int?j = 0; j < _nVertexCount; ++j ){_arrPath[i][j] = i;}}//for?( int?k = 0; k < _nVertexCount; ++k ){for?( int?i = 0; i < _nVertexCount; ++i ){for?( int?j = 0; j < _nVertexCount; ++j ){if?( _arrDis[i][k] + _arrDis[k][j] < _arrDis[i][j] ){// 找到更短路徑_arrDis[i][j] = _arrDis[i][k] + _arrDis[k][j];_arrPath[i][j] = _arrPath[k][j];}}}}}

OK，最后是輸出結果數據代碼：

void?printResult( int?_arrDis[][MAX_VERTEX_COUNT], int?_arrPath[][MAX_VERTEX_COUNT], int?_nVertexCount ){std::cout << "Origin -> Dest?? Distance??? Path"?<< std::endl;for?( int?i = 0; i < _nVertexCount; ++i ){for?( int?j = 0; j < _nVertexCount; ++j ){if?( i != j )?? // 節點不是自身{std::cout << i+1 << " -> "?<< j+1 << "\t\t";if?( INFINITE == _arrDis[i][j] )??? // i -> j 不存在路徑{std::cout << "INFINITE"?<< "\t\t";}else{std::cout << _arrDis[i][j] << "\t\t";// 由于我們查詢最短路徑是從后往前插，因此我們把查詢得到的節點// 壓入棧中，最后彈出以順序輸出結果。std::stack<int> stackVertices;int?k = j;do{k = _arrPath[i][k];stackVertices.push( k );} while?( k != i );//std::cout << stackVertices.top()+1;stackVertices.pop();unsigned int?nLength = stackVertices.size();for?( unsigned int?nIndex = 0; nIndex < nLength; ++nIndex ){std::cout << " -> "?<< stackVertices.top()+1;stackVertices.pop();}std::cout << " -> "?<< j+1 << std::endl;}}}}}

好了，是時候測試了，我們用的圖如下：

測試代碼如下：

int?main( void?){Graph myGraph;readGraphData( &myGraph );//int?arrDis[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];int?arrPath[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];// 先初始化arrDisfor?( int?i = 0; i < myGraph.nVertexCount; ++i ){for?( int?j = 0; j < myGraph.nVertexCount; ++j ){arrDis[i][j] = myGraph.arrArcs[i][j];}}floyd( arrDis, arrPath, myGraph.nVertexCount );//printResult( arrDis, arrPath, myGraph.nVertexCount );//system( "pause"?);return?0;}

如圖：