floyd算法實現(xiàn)思路及實例代碼
正如我們所知道的，F(xiàn)loyd算法用于求最短路徑。Floyd算法可以說是Warshall算法的擴展，三個for循環(huán)就可以解決問題，所以它的時間復雜度為O(n^3)。
Floyd算法的基本思想如下：從任意節(jié)點A到任意節(jié)點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過若干個節(jié)點X到B。所以，我們假設Dis(AB)為節(jié)點A到節(jié)點B的最短路徑的距離，對于每一個節(jié)點X，我們檢查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設置Dis(AB) = Dis(AX) + Dis(XB)，這樣一來，當我們遍歷完所有節(jié)點X，Dis(AB)中記錄的便是A到B的最短路徑的距離。
很簡單吧，代碼看起來可能像下面這樣：
for ( int i = 0; i < 節(jié)點個數(shù); ++i )
{
for ( int j = 0; j < 節(jié)點個數(shù); ++j )
{
for ( int k = 0; k < 節(jié)點個數(shù); ++k )
{
if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
{
// 找到更短路徑
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
}
}
}
但是這里我們要注意循環(huán)的嵌套順序，如果把檢查所有節(jié)點X放在最內(nèi)層，那么結(jié)果將是不正確的，為什么呢？因為這樣便過早的把i到j的最短路徑確定下來了，而當后面存在更短的路徑時，已經(jīng)不再會更新了。
讓我們來看一個例子，看下圖：
圖中紅色的數(shù)字代表邊的權重。如果我們在最內(nèi)層檢查所有節(jié)點X，那么對于A->B，我們只能發(fā)現(xiàn)一條路徑，就是A->B，路徑距離為9。而這顯然是不正確的，真實的最短路徑是A->D->C->B，路徑距離為6。造成錯誤的原因就是我們把檢查所有節(jié)點X放在最內(nèi)層，造成過早的把A到B的最短路徑確定下來了，當確定A->B的最短路徑時Dis(AC)尚未被計算。所以，我們需要改寫循環(huán)順序，如下：
for ( int k = 0; k < 節(jié)點個數(shù); ++k )
{
for ( int i = 0; i < 節(jié)點個數(shù); ++i )
{
for ( int j = 0; j < 節(jié)點個數(shù); ++j )
{
if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
{
// 找到更短路徑
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
}
}
}
這樣一來，對于每一個節(jié)點X，我們都會把所有的i到j處理完畢后才繼續(xù)檢查下一個節(jié)點。
那么接下來的問題就是，我們?nèi)绾握页鲎疃搪窂侥?？這里需要借助一個輔助數(shù)組Path，它是這樣使用的：Path(AB)的值如果為P，則表示A節(jié)點到B節(jié)點的最短路徑是A->...->P->B。這樣一來，假設我們要找A->B的最短路徑，那么就依次查找，假設Path(AB)的值為P，那么接著查找Path(AP)，假設Path(AP)的值為L，那么接著查找Path(AL)，假設Path(AL)的值為A，則查找結(jié)束，最短路徑為A->L->P->B。
那么，如何填充Path的值呢？很簡單，當我們發(fā)現(xiàn)Dis(AX) + Dis(XB) < Dis(AB)成立時，就要把最短路徑改為A->...->X->...->B，而此時，Path(XB)的值是已知的，所以，Path(AB) = Path(XB)。
好了，基本的介紹完成了，接下來就是實現(xiàn)的時候了，這里我們使用圖以及鄰接矩陣：
#define INFINITE 1000 // 最大值
#define MAX_VERTEX_COUNT 20 // 最大頂點個數(shù)
//////////////////////////////////////////////////////////////////////////
struct Graph
{
int arrArcs[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; // 鄰接矩陣
int nVertexCount; // 頂點數(shù)量
int nArcCount; // 邊的數(shù)量
};
//////////////////////////////////////////////////////////////////////////
首先，我們寫一個方法，用于讀入圖的數(shù)據(jù)：
void readGraphData( Graph *_pGraph )
{
std::cout << "請輸入頂點數(shù)量和邊的數(shù)量: ";
std::cin >> _pGraph->nVertexCount;
std::cin >> _pGraph->nArcCount;
std::cout << "請輸入鄰接矩陣數(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é)點不是自身
{
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";
// 由于我們查詢最短路徑是從后往前插，因此我們把查詢得到的節(jié)點
// 壓入棧中，最后彈出以順序輸出結(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;
}
}
}
}
}
好了，是時候測試了，我們用的圖如下：
測試代碼如下：
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;
}
如圖：
相關文章
這篇文中主要為大家詳細介紹了如何利用C語言實現(xiàn)經(jīng)典的掃雷小游戲。掃雷小游戲主要是利用字符數(shù)組、循環(huán)語句和函數(shù)實現(xiàn)，感興趣的小伙伴可以了解一下2022-10-10
這篇文章主要介紹了C++取得當前時間的方法,實例展示了通過系統(tǒng)函數(shù)獲取當前時間的實現(xiàn)方法,非常簡單易懂,需要的朋友可以參考下2014-10-10
這篇文章主要為大家詳細介紹了C語言版二值圖像統(tǒng)計連通區(qū)域的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C++類中的六大默認成員函數(shù)，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
本篇文章主要為大家介紹字符串模糊查詢的C語言程序編寫方法,有需要的朋友可以參考下2015-07-07
C語言字符函數(shù)isalnum()和iscntrl()詳解
大家好，本篇文章主要講的是C語言字符函數(shù)isalnum()和iscntrl()詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
這篇文章主要介紹了C++賦值運算符,C++當中允許類對象賦值，這是通過默認的重載賦值運算符實現(xiàn)的,下面我們就來介紹介紹該內(nèi)容吧，,需要的朋友可以參考一下2022-01-01
這篇文章主要介紹了C語言/C++讀取大文件數(shù)據(jù)的完整方式過程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-09-09
詳解在C++中顯式默認設置的函數(shù)和已刪除的函數(shù)的方法
這篇文章主要介紹了在C++中顯式默認設置的函數(shù)和已刪除的函數(shù)的方法,文中講到了C++11標準中的新特性,需要的朋友可以參考下2016-01-01
單值二叉樹你可能之前沒見過，如果二叉樹每個節(jié)點都具有相同的值，那么該二叉樹就是單值二叉樹，讓我們通過一個真題來深刻了解它吧2022-04-04