编辑代码

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

#define MaxVertex 10
#define INFINITY 65535

typedef int Vertex;
typedef struct AdjVNode *PtrToAdjVNode;
typedef struct GNode *PtrToGNode;
typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
typedef PtrToGNode LGraph;

struct ENode{
    Vertex V1,V2;
    int Weight;
};

struct AdjVNode{
    Vertex Adj;
    int Weight;
    PtrToAdjVNode next;
};

typedef struct VNode{
    PtrToAdjVNode FirstEdge; 
}AdjList[MaxVertex];

//图结点
struct GNode{
    int Nv;
    int Ne;
    AdjList G;
};

LGraph CreateGraph(int VertexNum);
void InsertEdge(LGraph Graph,Edge E);
LGraph BuildGraph();
void Dijkstra(LGraph Graph,Vertex s,int collected[],int path[],int dist[]);
Vertex FindMinDist(LGraph Graph,int dist[]);
void Inititial(LGraph Graph,int Nv,int dist[]);

void Inititial(LGraph Graph,int Nv,int dist[]){
    dist[Nv] = 0;
    if(Graph->G[Nv].FirstEdge != NULL){
        PtrToAdjVNode W = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        W = Graph->G[Nv].FirstEdge;
        while(W != NULL){
            dist[W->Adj] = W->Weight;
            W = W->next;
        }
    }
}

Vertex FindMinDist(LGraph Graph,int dist[]){
    int result = 0;
    for(int i = 0;i < Graph->Nv;i++){
        if(dist[i] > dist[i+1]){
            result = i+1;
        }
    }

    return result;
}

void Dijkstra(LGraph Graph,Vertex s,int collected[],int path[],int dist[]){
   while(1){
       //找到未收录顶点中dist最小者
       Vertex V = FindMinDist(Graph,dist);
       
       //不存在这样的顶点了,跳出循环
       if(collected[V]){
           break;
       }
       //否则,收录该顶点
       collected[V] = true;
       if(Graph->G[V].FirstEdge != NULL){
           PtrToAdjVNode W = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
           W = Graph->G[V].FirstEdge;
           while(W != NULL){
           if(collected[W->Adj] == false){
               if(dist[V] + W->Weight < dist[W->Adj]){
                   dist[W->Adj] = dist[V] + W->Weight;
                   path[W->Adj] = V;
               }
           }
           W = W->next;
        }
       }
   } 
}

LGraph BuildGraph(){
    LGraph Graph;
    Vertex VertexNum;
    
    printf("输入结点数:\n");
    scanf("%d",&VertexNum);
    Graph = CreateGraph(VertexNum);
    
    printf("输入边数:\n");
    scanf("%d",&Graph->Ne);

    if(Graph->Ne != 0){
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for(int i = 0;i < Graph->Nv;i++){
            printf("输入要插入的两个结点以及权重:\n");
            scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
            InsertEdge(Graph,E);
        }
    }

    return Graph;
}

void InsertEdge(LGraph Graph,Edge E){
    PtrToAdjVNode NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode)); 
    NewNode->Adj = E->V2;
    NewNode->Weight = E->Weight;
    NewNode->next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->Adj = E->V1;
    NewNode->Weight = E->Weight;
    NewNode->next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph CreateGraph(int VertexNum){
    LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    for(int i = 0;i < Graph->Nv;i++){
        Graph->G[i].FirstEdge = NULL;
    }
    
    return Graph;
}

int main () {
   LGraph Graph = BuildGraph();
   int dist[MaxVertex],collected[MaxVertex],path[MaxVertex];
   int Nv;

   //需要用到的数组初始化
   for(int i = 0;i < Graph->Nv;i++){
       dist[i] = INFINITY;
       path[i] = -1;
       collected[i] = false;
   }

   printf("输入要查找的单源最短路径的结点:\n");
   scanf("%d",&Nv);
   Inititial(Graph,Nv,dist);
   Dijkstra(Graph,Nv,collected,path,dist);

   for(int i = 0;i < Graph->Nv;i++){
       if(Graph->G[i].FirstEdge != NULL){
           PtrToAdjVNode p = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
           p = Graph->G[i].FirstEdge;
           while(p != NULL){
               printf("%d",p->Adj);
               p = p->next;
           }
       }
   }

   return 0;
}