C语言数据结构弗洛伊德算法-求两点之间最短路径长度

你的名字 2022-01-22 04:31 277阅读 0赞

/\*  
\*求有向网中的任意两点的最短路径  
\*弗洛伊德算法的核心是 运用一个path二维数组 和一个A二维数组  
\*path数组用来保存中间路径经过的节点  
\*A数组用来保存任意两个顶点之间的最短路径长度  
\*最后输出A数组运用了递归输出的思想  
\*先初始化path数组和A数组  
\*运用三层循环 （算法的核心） 计算任意两点之间的最短路径长度 将经过的节点的下标存储在path数组中去  
\*递增的思想  
\*创建一个有向网 输出一个临接矩阵  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define  OK 1
    #define ERROR 0
    #define   VERTEXNUM 100//最大顶点数
    #define  NAME_SIZE 255//字符串的最大长度
    #define MAX_INT 32726 //权重最大值
    typedef int Statu;//返回值的数据类型
    typedef  char*VertexType;//字符串的数据类型
    typedef int ArcType;//权值数组的数据类型
    typedef struct  amgraph
    {
        VertexType vexs[VERTEXNUM];//图的顶点数组
        ArcType arcs[VERTEXNUM][VERTEXNUM];//图的权值的二维数组
        int n;//图的顶点数
        int e;//图的边数
    }AMGraph;//图的结构体
    int  path[VERTEXNUM][VERTEXNUM];//用于保存进过的中间路径的节点的下标
    int A[VERTEXNUM][VERTEXNUM];//经过的路径节点的权值
    void main()
    {
        test();//测试函数
    
    }
    void test();//测试函数
    Statu create_DN(AMGraph*G);//创建有向网
    int Locate_vex(AMGraph*G,VertexType vex);//定位函数
    void Floyed_function(AMGraph*G);//弗洛伊德算法
    void Dispath(int A[][VERTEXNUM],int path[][VERTEXNUM],int n);
    //n代表当前图的顶点数
    //最短路径第一输出函数  主要用于输出权值
    void Ppath(int path[][VERTEXNUM],int i,int j);//用于输出路径节点的下标
    //创建一个有向网
    Statu create_DN(AMGraph*G)//创建有向网
    {
        int i,j;//循环变量
        VertexType  vex1,vex2;//字符串的临时变量
        int x,y;//定位函数的临时变量
        int now_weight;//当前的权重
        printf("请输入有向网的顶点数：");
           scanf("%d",&G->n);
           printf("请输入有向网的边数：");
             scanf("%d",&G->e);
             //初始化顶点的信息
             for(i=0;i<G->n;i++)
             {
                 G->vexs[i]=(VertexType)malloc(sizeof(char)*10);//动态申请存储空间
                 printf("顶点%d：",i+1);
                   scanf("%s",G->vexs[i]);
    
             }
             //初始化权值数组
             for(i=0;i<VERTEXNUM;i++)
                 for(j=0;j<VERTEXNUM;j++)
             {
                 G->arcs[i][j]=MAX_INT;//权值初始化
    
             }
             //初始化边的信息
             for(i=0;i<G->e;i++)
             {
                 vex1=(VertexType)malloc(sizeof(char)*10);//动态申请存储空间
                 vex2=(VertexType)malloc(sizeof(char)*10);//动态申请存储空间
                 printf("顶点：");
                 scanf("%s",vex1);
                 printf("邻接点：");
                 scanf("%s",vex2);
                 printf("请输入当前的权重：");
                 scanf("%d",&now_weight);
                 x=Locate_vex(G,vex1);
                 y=Locate_vex(G,vex2);
                 if(x==-1||y==-1)
                 {
                     return ERROR;
                 }
                 else
                 {
                     G->arcs[x][y]=now_weight;//创建的是有向网
                 }
    
            }
            return OK;
    }
    int Locate_vex(AMGraph*G,VertexType vex)
    {
        int index=0;
        while(index<G->n)
        {
            if(strcmp(vex,G->vexs[index])==0)
            {
                break;
            }
            else
            {
                index++;
            }
        }
          return (index==G->n ? -1 : index);
    }
    void Floyed_function(AMGraph*G)//弗洛伊德算法
    {
        int i,j;//循环变量
        int k;
        for(i=0;i<G->n;i++)
        for(j=0;j<G->n;j++)
         {
            path[i][j]=-1;//path数组初始化
             A[i][j]=G->arcs[i][j];
             //初始化A数组  有边的存在 存储权值 没有边的存在 即为无穷大
          }
        //算法的核心  三层循环
            for(k=0;k<G->n;k++)
              for(i=0;i<G->n;i++)
                for(j=0;j<G->n;j++)
                  if(A[i][j]>A[i][k]+A[k][j])
                    {
                        A[i][j]=A[i][k]+A[k][j];
                        path[i][j]=k;//存储路径
    
                    }
    
    
    
    
        Dispath(A,path,G->n);//输出任意两个邻接点的最短路径长度
    
    }
    void Ppath(int path[][VERTEXNUM],int i,int j)//输出最短路径经过的中间节点
    {
        int k;
        k=path[i][j];
        if(k==-1)//两个顶点之间无中间节点
        {
            printf("%d->",i);
            printf("%d",j);
        }
        else{
        Ppath(path,i,k);//递归的思想   输出最短路径经过的节点
        printf("%d->",k);
        Ppath(path,k,j);}
    
    }
    void Dispath(int A[][VERTEXNUM],int path[][VERTEXNUM],int n)//依次输出最短路径的权值
    {
        int i,j;//循环变量
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
               {
                   if(A[i][j]==MAX_INT)
    
                       if(i!=j)//排除顶点本身的情况
                       {
                           printf("从%d到%d没有路径\n",i,j);
    
                       }
                       else
                       {
                           printf("%d到%d的最短路径长度为\n",i,j);
                          // printf("path：");
                           printf("%d->",i);
                           Ppath(path,i,j);
                           printf("%d",j);
                           printf("路径长度为：%d\n",A[i][j]);
                       }
    
    
    
               }
    
    
    }
    
    void test()
    {
        int i,j;//循环变量
        AMGraph*G;
        G=(AMGraph*)malloc(sizeof(AMGraph));
        int result=create_DN(G);
        if(result==ERROR)
        {
            printf("有向网创建失败！\n");
            return ;
        }
        else//输出邻接矩阵
        {
            printf("该有向网的邻接矩阵为：\n");
            printf("\t");
            //输出第一行的顶点
             for(i=0;i<G->n;i++)
             {
                 printf("\t%s",G->vexs[i]);
             }
             printf("\n");//换行输出
             //输出边的信息
             for(i=0;i<G->n;i++)
             {
                   printf("\t%s",G->vexs[i]);
                     for(j=0;j<G->n;j++)
                       {
                           if(G->arcs[i][j]==MAX_INT)
                            printf("\t∞");
                           else
                            printf("\t%d",G->arcs[i][j]);
    
                        }
                        printf("\n");//换行
    
             }
        }
           printf("\n");
           printf("最短路径及其经过的节点为:\n");
           Floyed_function(G);
    
    }