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

輸入：

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

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  //無(wú)窮大#define MAXN 20

int n;   //頂點(diǎn)個(gè)數(shù)int Edge[MAXN][MAXN];  //鄰接矩陣int A[MAXN][MAXN];   //
int path[MAXN][MAXN];  //
void Floyd( ) //假定圖的鄰接矩陣和頂點(diǎn)個(gè)數(shù)已經(jīng)讀進(jìn)來(lái)了{(lán)
int i, j, k;
for( i=0; i<n; i++ )
    {
for( j=0; j<n; j++ )
        {
            A[i][j]= Edge[i][j];  //對(duì)a[ ][ ]初始化 if( i!=j && A[i][j]<INF )  path[i][j] = i; //i到j(luò)有路徑 else path[i][j] = -1;  //從i到j(luò)沒(méi)有直接路徑        }
    }
//從A(-1)遞推到A(0), A(1), ..., A(n-1),
//或者理解成依次將v0,v1,...,v(n-1)作為中間頂點(diǎn)  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;  //邊的起點(diǎn)和終點(diǎn)及權(quán)值    scanf( "%d", &n );  //讀入頂點(diǎn)個(gè)數(shù)n  for( i=0; i<n; i++ )  //設(shè)置鄰接矩陣中每個(gè)元素的初始值為INF    {
for( j=0; j<n; j++ )  Edge[i][j] = INF;
    }
for( i=0; i<n; i++ )  //設(shè)置鄰接矩陣中對(duì)角線上的元素值為0    {
        Edge[i][i]= 0;
    }
while( 1 )
    {
        scanf("%d%d%d", &u, &v, &w );  //讀入邊的起點(diǎn)和終點(diǎn)   if( u==-1 && v==-1 && w==-1 )break;
        Edge[u][v]= w;  //構(gòu)造鄰接矩陣    }
    Floyd( );//求各對(duì)頂點(diǎn)間的最短路徑  int shortest[MAXN];  //輸出最短路徑上的各個(gè)頂點(diǎn)時(shí)存放各個(gè)頂點(diǎn)的序號(hào)  for( i=0; i<n; i++ )
    {
for( j=0; j<n; j++ )
        {
if( i==j )continue;  //跳過(guò)            printf( "%d=>%d	%d	", i, j, A[i][j] );  //輸出頂點(diǎn)i到頂點(diǎn)j的最短路徑長(zhǎng)度
//以下代碼用于輸出頂點(diǎn)0到頂點(diǎn)i的最短路徑            memset( shortest, 0, sizeof(shortest) );
int k = 0;  //k表示shortest數(shù)組中最后一個(gè)元素的下標(biāo)            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;
}

名稱(chēng)欄目：Floyd得實(shí)現(xiàn)-創(chuàng)新互聯(lián)
文章源于：http://m.rwnh.cn/article40/iieeo.html

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

廣告

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