測試數據：

輸入：

目前累計服務客戶成百上千家，積累了豐富的產品開發及服務經驗。以網站設計水平和技術實力，樹立企業形象，為客戶提供成都網站設計、成都網站建設、網站策劃、網頁設計、網絡營銷、VI設計、網站改版、漏洞修補等服務。成都創新互聯公司始終以務實、誠信為根本，不斷創新和提高建站品質，通過對領先技術的掌握、對創意設計的研究、對客戶形象的視覺傳遞、對應用系統的結合，為客戶提供更好的一站式互聯網解決方案，攜手廣大客戶，共同發展進步。

4
0 1 1
0 3 4
1 2 9
1 3 2
2 0 3
2 1 5
2 3 8
3 2 6
-1 -1 -1

輸出：

0=>1  1  0→1
0=>2  9  0→1→3→2
0=>3  3  0→1→3
1=>0  11  1→3→2→0
1=>2  8  1→3→2
1=>3  2  1→3
2=>0  3  2→0
2=>1  4  2→0→1
2=>3  6  2→0→1→3
3=>0  9  3→2→0
3=>1  10  3→2→0→1
3=>2  6   3→2

#include <cstdio>
#include<string>
#define INF    1000000  //無窮大#define MAXN 20

int n;   //頂點個數int Edge[MAXN][MAXN];  //鄰接矩陣int A[MAXN][MAXN];   //
int path[MAXN][MAXN];  //
void Floyd( ) //假定圖的鄰接矩陣和頂點個數已經讀進來了{
int i, j, k;
for( i=0; i<n; i++ )
    {
for( j=0; j<n; j++ )
        {
            A[i][j]= Edge[i][j];  //對a[ ][ ]初始化 if( i!=j && A[i][j]<INF )  path[i][j] = i; //i到j有路徑 else path[i][j] = -1;  //從i到j沒有直接路徑        }
    }
//從A(-1)遞推到A(0), A(1), ..., A(n-1),
//或者理解成依次將v0,v1,...,v(n-1)作為中間頂點  for( k=0; k<n; k++ )
    {
for( i=0; i<n; i++ )
        {
for( j=0; j<n; j++ )
            {
if( k==i || k==j )continue;
if( A[i][k] + A[k][j] < A[i][j] )
                {
                    A[i][j]= A[i][k] + A[k][j] ;
                    path[i][j]= path[k][j];
                }
            }
        }
    }
}

int main( )
{
int i, j;  //循環變量  int u, v, w;  //邊的起點和終點及權值    scanf( "%d", &n );  //讀入頂點個數n  for( i=0; i<n; i++ )  //設置鄰接矩陣中每個元素的初始值為INF    {
for( j=0; j<n; j++ )  Edge[i][j] = INF;
    }
for( i=0; i<n; i++ )  //設置鄰接矩陣中對角線上的元素值為0    {
        Edge[i][i]= 0;
    }
while( 1 )
    {
        scanf("%d%d%d", &u, &v, &w );  //讀入邊的起點和終點   if( u==-1 && v==-1 && w==-1 )break;
        Edge[u][v]= w;  //構造鄰接矩陣    }
    Floyd( );//求各對頂點間的最短路徑  int shortest[MAXN];  //輸出最短路徑上的各個頂點時存放各個頂點的序號  for( i=0; i<n; i++ )
    {
for( j=0; j<n; j++ )
        {
if( i==j )continue;  //跳過            printf( "%d=>%d	%d	", i, j, A[i][j] );  //輸出頂點i到頂點j的最短路徑長度
//以下代碼用于輸出頂點0到頂點i的最短路徑            memset( shortest, 0, sizeof(shortest) );
int k = 0;  //k表示shortest數組中最后一個元素的下標            shortest[k] = j;
while( path[i][ shortest[k] ] != i )
            {
                k++; shortest[k] = path[i][ shortest[k-1] ];
            }
            k++; shortest[k] = i;
for( int t=k; t>0; t-- )
                printf("%d→", shortest[t] );
            printf("%d
", shortest[0] );
        }
    }
return 0;
}

名稱欄目：Floyd得實現-創新互聯
文章源于：http://vcdvsql.cn/article40/iieeo.html

成都網站建設公司_創新互聯，為您提供網站制作、服務器托管、響應式網站、外貿建站、微信公眾號、網頁設計公司

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯