正如我們所知道的，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 )
{
// 先初始化_arrPath
for ( 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];
// 先初始化arrDis
for ( 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;
}
如圖：
