題目描述

在帶權有向圖G中，求G中的任意一對頂點間的最短路徑問題，也是十分常見的一種問題。

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

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

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

?

在本題中，讀入一個有向圖的帶權鄰接矩陣（即數組表示），建立有向圖并按照以上描述中的算法求出每一對頂點間的最短路徑長度。

?

輸入

輸入的第一行包含1個正整數n，表示圖中共有n個頂點。其中n不超過50。

以后的n行中每行有n個用空格隔開的整數。對于第i行的第j個整數，如果大于0，則表示第i個頂點有指向第j個頂點的有向邊，且權值為對應的整數值；如果這個整數為0，則表示沒有i指向j的有向邊。當i和j相等的時候，保證對應的整數為0。

輸出

共有n行，每行有n個整數，表示源點至每一個頂點的最短路徑長度。如果不存在從源點至相應頂點的路徑，輸出-1。對于某個頂點到其本身的最短路徑長度，輸出0。

請在每個整數后輸出一個空格，并請注意行尾輸出換行。

樣例輸入

<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>

提示

?

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

?

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

?

另外需要注意的是，為了更方便的表示頂點間的不可達狀態，可以使用一個十分大的值作為標記。而在題目描述中的算法示例使用了另外一個三維數組對其進行表示，這使原本的O(n3)時間復雜度增長到了O(n4)，這也是需要自行修改的部分。

?

#include <iostream> using namespace std;const int maxn = 50; const int inf = 1000000000; int G[maxn][maxn]; int d[maxn][maxn]; int n; //n個頂點，不超過50void ShortestPan_FLOYD() {int v, w, i, j, k;for(v = 0; v < n; v++){for(w = 0; w < n; w++){d[v][w] = G[v][w];}}for(k = 0; k < n; k++){for(i = 0; i < n; i++){for(j = 0; j < n; j++){if(d[i][k] + d[k][j] < d[i][j]){d[i][j] = d[i][k] + d[k][j];}}}} }int main() {scanf("%d", &n);for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){scanf("%d", &G[i][j]);if(G[i][j] == 0 && i != j)//不可達{G[i][j] = inf;}}}ShortestPan_FLOYD();for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(d[i][j] == 0){if(i == j) printf("0 ");}else if(d[i][j] == inf){printf("-1 ");}else{printf("%d ", d[i][j]);}}printf("\n");}return 0; }

?

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。