測試數(shù)據(jù)：

輸入：

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

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;   //頂點個數(shù)int Edge[MAXN][MAXN];  //鄰接矩陣int A[MAXN][MAXN];   //
int path[MAXN][MAXN];  //
void Floyd( ) //假定圖的鄰接矩陣和頂點個數(shù)已經(jīng)讀進來了{
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(luò)有路徑 else path[i][j] = -1;  //從i到j(luò)沒有直接路徑        }
    }
//從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;  //循環(huán)變量  int u, v, w;  //邊的起點和終點及權(quán)值    scanf( "%d", &n );  //讀入頂點個數(shù)n  for( i=0; i<n; i++ )  //設(shè)置鄰接矩陣中每個元素的初始值為INF    {
for( j=0; j<n; j++ )  Edge[i][j] = INF;
    }
for( i=0; i<n; i++ )  //設(shè)置鄰接矩陣中對角線上的元素值為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;  //構(gòu)造鄰接矩陣    }
    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數(shù)組中最后一個元素的下標            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得實現(xiàn)-創(chuàng)新互聯(lián)
文章源于：http://www.chinadenli.net/article40/iieeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、服務(wù)器托管、響應(yīng)式網(wǎng)站、外貿(mào)建站、微信公眾號、網(wǎng)頁設(shè)計公司

廣告

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