您好,登錄后才能下訂單哦!
小編給大家分享一下C++怎么實(shí)現(xiàn)多源最短路徑之Floyd算法,希望大家閱讀完這篇文章之后都有所收獲,下面讓我們一起去探討吧!
C++實(shí)現(xiàn)多源最短路徑之Floyd算法,具體如下:
#include<cstdio> #include<cstring> #include<iostream> #define MAX 999 using namespace std; int n,m; int e[MAX][MAX]; void Init() { for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { if(i==j) e[i][j]=0; else e[i][j]=MAX; } } void Input() { int a,b,c; for(int i=1; i<=m; ++i) { cin>>a>>b>>c; e[a][b]=c; } } void Floyd() { for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; } void Output() { for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) cout<<"dis["<<i<<"]["<<j<<"] = "<<e[i][j]<<endl; } int main() { while(1) { cout<<"n"<<endl;//頂點(diǎn)個(gè)數(shù) cin>>n; if(!n) break; cout<<"m"<<endl;//邊的個(gè)數(shù) cin>>m; Init(); Input(); Floyd(); Output(); } }
Floyd算法是求多點(diǎn)最短路徑的一種算法,其核心代碼為
void Floyd() { for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; }
看完了這篇文章,相信你對(duì)“C++怎么實(shí)現(xiàn)多源最短路徑之Floyd算法”有了一定的了解,如果想了解更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。