正如我們所知道的，F(xiàn)loyd算法用于求最短路徑。Floyd算法可以說(shuō)是Warshall算法的擴(kuò)展，三個(gè)for循環(huán)就可以解決問(wèn)題，所以它的時(shí)間復(fù)雜度為O(n^3)。
Floyd算法的基本思想如下：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)X到B。所以，我們假設(shè)Dis(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)X，我們檢查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設(shè)置Dis(AB) = Dis(AX) + Dis(XB)，這樣一來(lái)，當(dāng)我們遍歷完所有節(jié)點(diǎn)X，Dis(AB)中記錄的便是A到B的最短路徑的距離。
很簡(jiǎn)單吧，代碼看起來(lái)可能像下面這樣：
for ( int i = 0; i < 節(jié)點(diǎn)個(gè)數(shù); ++i )
{
for ( int j = 0; j < 節(jié)點(diǎn)個(gè)數(shù); ++j )
{
for ( int k = 0; k < 節(jié)點(diǎn)個(gè)數(shù); ++k )
{
if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
{
// 找到更短路徑
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
}
}
}
但是這里我們要注意循環(huán)的嵌套順序，如果把檢查所有節(jié)點(diǎn)X放在最內(nèi)層，那么結(jié)果將是不正確的，為什么呢？因?yàn)檫@樣便過(guò)早的把i到j(luò)的最短路徑確定下來(lái)了，而當(dāng)后面存在更短的路徑時(shí)，已經(jīng)不再會(huì)更新了。
讓我們來(lái)看一個(gè)例子，看下圖：
圖中紅色的數(shù)字代表邊的權(quán)重。如果我們?cè)谧顑?nèi)層檢查所有節(jié)點(diǎn)X，那么對(duì)于A->B，我們只能發(fā)現(xiàn)一條路徑，就是A->B，路徑距離為9。而這顯然是不正確的，真實(shí)的最短路徑是A->D->C->B，路徑距離為6。造成錯(cuò)誤的原因就是我們把檢查所有節(jié)點(diǎn)X放在最內(nèi)層，造成過(guò)早的把A到B的最短路徑確定下來(lái)了，當(dāng)確定A->B的最短路徑時(shí)Dis(AC)尚未被計(jì)算。所以，我們需要改寫(xiě)循環(huán)順序，如下：
for ( int k = 0; k < 節(jié)點(diǎn)個(gè)數(shù); ++k )
{
for ( int i = 0; i < 節(jié)點(diǎn)個(gè)數(shù); ++i )
{
for ( int j = 0; j < 節(jié)點(diǎn)個(gè)數(shù); ++j )
{
if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
{
// 找到更短路徑
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
}
}
}
這樣一來(lái)，對(duì)于每一個(gè)節(jié)點(diǎn)X，我們都會(huì)把所有的i到j(luò)處理完畢后才繼續(xù)檢查下一個(gè)節(jié)點(diǎn)。
那么接下來(lái)的問(wèn)題就是，我們?nèi)绾握页鲎疃搪窂侥兀窟@里需要借助一個(gè)輔助數(shù)組Path，它是這樣使用的：Path(AB)的值如果為P，則表示A節(jié)點(diǎn)到B節(jié)點(diǎn)的最短路徑是A->...->P->B。這樣一來(lái)，假設(shè)我們要找A->B的最短路徑，那么就依次查找，假設(shè)Path(AB)的值為P，那么接著查找Path(AP)，假設(shè)Path(AP)的值為L(zhǎng)，那么接著查找Path(AL)，假設(shè)Path(AL)的值為A，則查找結(jié)束，最短路徑為A->L->P->B。
那么，如何填充Path的值呢？很簡(jiǎn)單，當(dāng)我們發(fā)現(xiàn)Dis(AX) + Dis(XB) < Dis(AB)成立時(shí)，就要把最短路徑改為A->...->X->...->B，而此時(shí)，Path(XB)的值是已知的，所以，Path(AB) = Path(XB)。
好了，基本的介紹完成了，接下來(lái)就是實(shí)現(xiàn)的時(shí)候了，這里我們使用圖以及鄰接矩陣：
#define INFINITE 1000 // 最大值
#define MAX_VERTEX_COUNT 20 // 最大頂點(diǎn)個(gè)數(shù)
//////////////////////////////////////////////////////////////////////////
struct Graph
{
int arrArcs[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; // 鄰接矩陣
int nVertexCount; // 頂點(diǎn)數(shù)量
int nArcCount; // 邊的數(shù)量
};
//////////////////////////////////////////////////////////////////////////
首先，我們寫(xiě)一個(gè)方法，用于讀入圖的數(shù)據(jù)：
void readGraphData( Graph *_pGraph )
{
std::cout << "請(qǐng)輸入頂點(diǎn)數(shù)量和邊的數(shù)量: ";
std::cin >> _pGraph->nVertexCount;
std::cin >> _pGraph->nArcCount;
std::cout << "請(qǐng)輸入鄰接矩陣數(shù)據(jù):" << 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，最后是輸出結(jié)果數(shù)據(jù)代碼：
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 ) // 節(jié)點(diǎn)不是自身
{
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";
// 由于我們查詢(xún)最短路徑是從后往前插，因此我們把查詢(xún)得到的節(jié)點(diǎn)
// 壓入棧中，最后彈出以順序輸出結(jié)果。
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;
}
}
}
}
}
好了，是時(shí)候測(cè)試了，我們用的圖如下：
測(cè)試代碼如下：
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;
}
如圖：
