題目描述

在帶權(quán)有向圖G中，求G中的任意一對(duì)頂點(diǎn)間的最短路徑問題，也是十分常見的一種問題。

解決這個(gè)問題的一個(gè)方法是執(zhí)行n次迪杰斯特拉算法，這樣就可以求出每一對(duì)頂點(diǎn)間的最短路徑，執(zhí)行的時(shí)間復(fù)雜度為O(n3)。

而另一種算法是由弗洛伊德提出的，時(shí)間復(fù)雜度同樣是O(n3)，但算法的形式簡單很多。

可以將弗洛伊德算法描述如下：

在本題中，讀入一個(gè)有向圖的帶權(quán)鄰接矩陣（即數(shù)組表示），建立有向圖并按照以上描述中的算法求出每一對(duì)頂點(diǎn)間的最短路徑長度。

?

輸入

輸入的第一行包含1個(gè)正整數(shù)n，表示圖中共有n個(gè)頂點(diǎn)。其中n不超過50。

以后的n行中每行有n個(gè)用空格隔開的整數(shù)。對(duì)于第i行的第j個(gè)整數(shù)，如果大于0，則表示第i個(gè)頂點(diǎn)有指向第j個(gè)頂點(diǎn)的有向邊，且權(quán)值為對(duì)應(yīng)的整數(shù)值；如果這個(gè)整數(shù)為0，則表示沒有i指向j的有向邊。當(dāng)i和j相等的時(shí)候，保證對(duì)應(yīng)的整數(shù)為0。

輸出

共有n行，每行有n個(gè)整數(shù)，表示源點(diǎn)至每一個(gè)頂點(diǎn)的最短路徑長度。如果不存在從源點(diǎn)至相應(yīng)頂點(diǎn)的路徑，輸出-1。對(duì)于某個(gè)頂點(diǎn)到其本身的最短路徑長度，輸出0。

請(qǐng)?jiān)诿總€(gè)整數(shù)后輸出一個(gè)空格，并請(qǐng)注意行尾輸出換行。

樣例輸入

<span style="color:#333333">4 0 3 0 1 0 0 4 0 2 0 0 0 0 0 1 0 </span>

樣例輸出

<span style="color:#333333">0 3 2 1 6 0 4 7 2 5 0 3 3 6 1 0 </span>

提示

?

在本題中，需要按照題目描述中的算法完成弗洛伊德算法，并在計(jì)算最短路徑的過程中將每個(gè)頂點(diǎn)是否可達(dá)記錄下來，直到求出每一對(duì)頂點(diǎn)的最短路徑之后，算法才能夠結(jié)束。

?

相對(duì)于迪杰斯特拉算法，弗洛伊德算法的形式更為簡單。通過一個(gè)三重循環(huán)，弗洛伊德算法可以方便的求出每一對(duì)頂點(diǎn)間的最短距離。

?

另外需要注意的是，為了更方便的表示頂點(diǎn)間的不可達(dá)狀態(tài)，可以使用一個(gè)十分大的值作為標(biāo)記。而在題目描述中的算法示例使用了另外一個(gè)三維數(shù)組對(duì)其進(jìn)行表示，這使原本的O(n3)時(shí)間復(fù)雜度增長到了O(n4)，這也是需要自行修改的部分。

?

?

#include<cstdio> #include<algorithm> #include<iostream> using namespace std;int n,m,T; const int INF = 0x3fffffff; const int MAXV = 100;int dis[MAXV][MAXV]; void Floyd() {for (int k=0;k<n;k++){for (int i=0;i<n;i++){for (int j=0;j<n;j++){if (dis[i][k] != INF && dis[k][j]!=INF&&dis[i][k] +dis[k][j]<dis[i][j]){dis[i][j] = dis[i][k] + dis[k][j];}}}} }int main() {int u,v,w;fill(dis[0],dis[0]+MAXV*MAXV , INF);cin>>n;for (int i=0;i<n;i++){for (int j=0;j<n;j++){cin>>dis[i][j];if (dis[i][j]==0 && i!=j)dis[i][j] = INF;}} Floyd();for (int i=0;i<n;i++){for (int j=0;j<n;j++){if (dis[i][j]==INF)cout<<"-1"<<" ";elsecout<<dis[i][j]<<" ";}cout<<endl;}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Romantic-Chopin/p/10253053.html

總結(jié)

以上是生活随笔為你收集整理的Codeup 问题 B: 算法7-16：弗洛伊德最短路径算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。