利用floyd算法求最短路径长度与并输出路径

àì夳堔傛蜴生んèń 2022-12-28 00:45 102阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #define MAX 1000
    typedef struct SHORTRSTPATH_STRU
    { 
        int size;//图中节点的个数
        int**pathLen;//二位数组保存每对顶点中的最短路径长度
        int **nextVex;//二维数组保存vi到vj最短路径上vi后续节点的下标
    }ShortPath;
    typedef struct GRAPHMATRIX_STRU
    { 
        int size;
        int **graph;
    }GraphMatrix;
    
    GraphMatrix* InitGraph(int num)
    { 
        int i,j;
        GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
        graphMatrix->size=num;
        graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
        for(i=0;i<graphMatrix->size;i++)
            graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
        for(i=0;i<graphMatrix->size;i++)
        { 
            for(j=0;j<graphMatrix->size;j++)
            graphMatrix->graph[i][j]=MAX;
    
        }
        return graphMatrix;
    }
    void ReadMatrix(GraphMatrix*graphMatrix)
    { 
        int vex1,vex2,weight;
        scanf("%d%d%d",&vex1,&vex2,&weight);
        while(vex1!=0||vex2!=0)
        { 
            graphMatrix->graph[vex1][vex2]=weight;
            scanf("%d%d%d",&vex1,&vex2,&weight);
        }
    
    }
    
    ShortPath*floyd(GraphMatrix*graphMatrix)
    { 
        int i,j,vex;
        ShortPath *shortPath=NULL;
        shortPath=(ShortPath*)malloc(sizeof(ShortPath));
        shortPath->size=graphMatrix->size;
        //分配空间二维数组
        shortPath->nextVex=(int**)malloc(sizeof(int*)*shortPath->size);
        for(i=0;i<shortPath->size;i++)
        shortPath->nextVex[i]=(int*)malloc(sizeof(int)*shortPath->size);
        //分配空间二维数组
        shortPath->pathLen=(int**)malloc(sizeof(int*)*shortPath->size);
        for(i=0;i<shortPath->size;i++)
            shortPath->pathLen[i]=(int*)malloc(sizeof(int)*shortPath->size);
        //初始化
        for(i=0;i<shortPath->size;i++)
        { 
            for(j=0;j<shortPath->size;j++)
            {    
                //为了不破坏图的原有结构，使用辅助数组进行数据的迭代
                shortPath->pathLen[i][j]=graphMatrix->graph[i][j];
                if(shortPath->pathLen[i][j]==MAX)
                    shortPath->nextVex[i][j]=-1;
                else
                    shortPath->nextVex[i][j]=j;
            }
        }
        //正式开始计算
        for(vex=0;vex<graphMatrix->size;vex++)
        { 
            for(i=0;i<graphMatrix->size;i++)
            { 
                for(j=0;j<graphMatrix->size;j++)
                { 
                    if(shortPath->pathLen[i][vex]==MAX||shortPath->pathLen[vex][j]==MAX)
                        continue;
                        //路径更短，则更新
                    if(shortPath->pathLen[i][vex]+shortPath->pathLen[vex][j]<shortPath->pathLen[i][j])
                    { 
                        shortPath->pathLen[i][j]=shortPath->pathLen[i][vex]+shortPath->pathLen[vex][j];
                        shortPath->nextVex[i][j]=shortPath->nextVex[i][vex];
                    }
                }
            }
    
        }
        return shortPath;
    }
    int main()
    {   
        //最短路径测试
       GraphMatrix*graphMatrix=NULL;
       ShortPath*shortPath=NULL;
       int i,j,k,e,maxdistan[6],min=0;
       graphMatrix=InitGraph(6);
       ReadMatrix(graphMatrix);//读图
       shortPath=floyd(graphMatrix);//使用floyd算法
       for(i=0;i<graphMatrix->size;i++)
       {    
           
           for(j=0;j<graphMatrix->size;j++)
           { 
               if(i!=j&&shortPath->pathLen[i][j]!=MAX)
               { 
                   printf("从%d到%d的最短路径长度为%d,具体路径为",i,j,shortPath->pathLen[i][j]);
                   printf("%d",i);//输出起点
                   k=i;//从起点出发，寻找完整路径
                   while(k!=j)
                   { 
                       k=shortPath->nextVex[k][j];
                       printf("->%d",k);//将途径点输出
                   }
                   printf("\n");
                   /*if(min<shortPath->pathLen[i][j]) { min=shortPath->pathLen[i][j]; maxdistan[i]=min; } if(i==0) { printf("%d->%d:%d",i,j,shortPath->pathLen[i][j]); printf("\n"); printf("%d",i); k=i; while(k!=j) { k=shortPath->nextVex[k][j]; printf("->%d",k); } printf("\n"); }*/
               }
           }
       }
       return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a8c563b4208746dc98de032990274aa4.png