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 <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得实现-创新互联
文章源于：https://www.cdcxhl.com/article40/iieeo.html

成都网站建设公司_创新互联，为您提供网站制作、服务器托管、响应式网站、外贸建站、微信公众号、网页设计公司

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容