C语言数据结构迪杰斯特拉算法-求源节点到各个节点的最短路径长度

怼烎@ 2022-01-22 04:31 65阅读 0赞

/\*  
\*迪杰斯特拉算法  
\*求源节点到其他各个节点的最短路径长度  
\*定义一个path数组 用来保存上一次的路径节点  
\*定义一个d数组 用来保存源节点到各个节点的最小路径  
\*定义一个s数组 用来保存已经找到最小路径的下标 定义为bool型全局变量  
\*最后遍历并打印d数组  
\*/

#include<stdio.h>
    #include<stdio.h>
    #include<string.h>
    #define VERTEXNUM 100//顶点数
    #define NAME_SIZE 255//字符串的最大长度
    #define MAX_INT 32762//权值最大值
    #define OK 1
    #define ERROR 0
    typedef  int Statu;//自定义状态数据类型
    typedef  char* VertexType;//顶点值数据类型
    typedef int ArcType;//权值的数据类型
    typedef struct amgraph
    {
        VertexType vex[VERTEXNUM];//顶点数组
        ArcType Arcs[VERTEXNUM][VERTEXNUM];//权值的二维数组
        int n;//图的顶点数
        int e;//图的边数
    }AMGraph;//有向网的数据结构
    int path[VERTEXNUM];//记录上一步节点
    int D[VERTEXNUM];//记录源节点到每一个顶点的最短路径
    int s[VERTEXNUM]={0};//用于记录该节点是否已经求得最短路径长度
    Statu create_DN(AMGraph*G);//创建有向网
    int Locate_vex(AMGraph*G,VertexType vex);//定位函数
    void  test();//测试函数
    void  shorttestpath_DIJ(AMGraph*G,int n);//迪杰斯特拉算法
    void main()
    {
          test();//测试函数
    }
    Statu create_DN(AMGraph*G)//创建有向网
    {
        int i,j;//循环变量
        VertexType vex1;//创建字符串临时变量
        VertexType vex2;
        int x,y;
        int now_weight;//当前的权重
        //创建有向网
        printf("请输入有向网的顶点数：");
        scanf("%d",&G->n);
        printf("请输入有向网的边数：");
        scanf("%d",&G->e);
    
        //初始化顶点信息
        for(i=0;i<G->n;i++)
        {
            printf("顶点：");
            G->vex[i]=(VertexType)malloc(sizeof(char)*10);
            scanf("%s",G->vex[i]);
        }
        //初始化权值数组
         for(i=0;i<VERTEXNUM;i++)
            for(j=0;j<VERTEXNUM;j++)
         {
             G->Arcs[i][j]=MAX_INT;//初始化权值
         }
        //初始化边
    
      for(j=0;j<G->e;j++)
        {
            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->vex[index])==0)
                break;
            else
                index++;
        }
          return (index==G->n ? -1:index);//三目运算符
    }
    //迪杰斯特拉算法
    void shorttestpath_DIJ(AMGraph*G,int n)
    {
        int i;
        int j,k;
        int min;
        int v;//保存最小路径节点的下标
        int v0=n;
        //Locate_vex(G,vex);//定位第一个节点的数组下标
       // printf("%d",v0);
        //初始化D数组和s数组
        for(i=0;i<G->n;i++)
        {
            D[i]=G->Arcs[v0][i];//初始化各个节点到源节点的权值
            if(D[i]<MAX_INT)
            {
                path[i]=0;//说明源节点和该顶点之间有边的存在
    
            }
            else
            {
                path[i]=-1;//说明之间没有边的存在
            }
    
    
        }
        s[v0]=OK;//源节点到源节点本身路径最短
        D[v0]=0;//源节点自身路径设置为0（本身到本身）
        //筛选最短路径的源节点到各个节点的最小路径的值存在D数组中去
        for(i=0;i<G->n;i++)
        {//在D数组中筛选最小路径  （未曾求得最小路径的情况下）
            min=MAX_INT;
            for(j=0;j<G->n;j++)
            {
                if(s[j]==0&&min>D[j])
                {
                    v=j;//得到最短路径的邻接下标
                    min=D[j];//找到D数组中的最短路径
    
                }
            }
            s[v]=OK;//已经求得其节点的最短路径   在函数的方法中起到至关重要的作用
            //利用递增的方法继续搜索 与V节点相邻的节点的最短路径
            for(k=0;k<G->n;k++)
            {
                if(s[k]==ERROR&&D[k]>D[v]+G->Arcs[v][k])//递增实现  算法的核心
                //与v相邻节点的权值和v在D数组中的值 递增的思想
                {
                    D[k]=D[v]+G->Arcs[v][k];
                    path[k]=v;//记录上一次的最小路径的节点
                }
    
            }
    
        }
    }
    void test()
    {
        int i,j;
        char c='A';
        AMGraph*G;
        G=(AMGraph*)malloc(sizeof(AMGraph));
        int result=create_DN(G);
        if(result==ERROR)
        {
            printf("创建有向网失败!\n");
            return ;
    
        }
        //输出该有向网
        printf("有向网的邻接矩阵为:\n");
        printf("\t");
        //输出第一行的顶点
        for(i=0;i<G->n;i++)
            printf("\t%s",G->vex[i]);
          printf("\n");
          //输出权值数组
          for(i=0;i<G->n;i++)
          {
              printf("\t%s",G->vex[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");
    
          shorttestpath_DIJ(G,0);
          for(i=1;i<G->n;i++)
          {
              if(D[i]==MAX_INT)
              {
                  printf("该节点%s与源节点之间不连通\n",G->vex[i]);
    
              }
              else
              {
                  printf("%c到%s的最短路径为%d\n",'A',G->vex[i],D[i]);
              }
    
          }
    }