Floyd得实现-创新互联

测试数据：

输入：

目前累计服务客户成百上千家，积累了丰富的产品开发及服务经验。以网站设计水平和技术实力，树立企业形象，为客户提供成都网站设计、成都网站建设、网站策划、网页设计、网络营销、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 
#include
#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%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得实现-创新互联
本文URL：http://cxhlcq.com/article/iieeo.html