求最短路径迪杰斯特拉算法

代码运行截图：

完整代码：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 20
#define MAX 999

typedef struct ArcNode{        //边表 
    int adjvex;                //边表中是顶点号！！ 
    struct ArcNode *next;
    int weight;
}ArcNode;

typedef struct VNode{        //主表 
    int num;                //主表中是顶点值！！ 
    struct ArcNode *first; 
}VNode,AdjList[MaxSize];

typedef struct{                    
    AdjList Ver;
    int vernum,edgenum;
}Graph;

void CreateGraph(Graph &G)
{
    int i,j,x;
    G.edgenum=0;
    G.vernum=0;
    
    printf("顶点个数:");
    scanf("%d",&G.vernum);
    
    printf("输入顶点表:\n");
    for(i=0;i<G.vernum;i++)
        scanf("%d",&G.Ver[i].num);
    
    printf("输入边表:\n");
    for(i=0;i<G.vernum;i++)
    {
        printf("与%d相连的顶点下标:\n",G.Ver[i].num);
        G.Ver[i].first=(ArcNode*)malloc(sizeof(ArcNode));
        G.Ver[i].first->next=NULL;
        ArcNode *p=G.Ver[i].first;
        for(j=0;j<G.vernum;j++)
        {
            scanf("%d",&x);
            if(x!=-1)
            {
                ArcNode *node=(ArcNode*)malloc(sizeof(ArcNode));
                node->next=NULL;
                node->adjvex=x;
                p->next=node;
                p=node;
                printf("输入该边的权值:");
                scanf("%d",&node->weight);
                G.edgenum++;    
            }
            else
                break;
        }
    }
}

void displayGraph(Graph G)
{
    int i;
    ArcNode *p=NULL;
    printf("顶点表:");
    for(i=0;i<G.vernum;i++)
        printf("%d    ",G.Ver[i].num);
    printf("\n");
    printf("边表:\n");
    for(i=0;i<G.vernum;i++)
    {
        printf("%d    -->",G.Ver[i].num);
        p=G.Ver[i].first->next;
        while(p)
        {
            printf("--权重为%d-->%d",p->weight,p->adjvex);
            p=p->next;
        }
        printf("\n");
    }
}

void dijkstra(Graph G,int start)
{
    int dist[G.vernum];
    bool visited[G.vernum];
    int i,j;
    for(i=0;i<G.vernum;i++)
    {
        dist[i]=MAX;
        visited[i]=false;    
    }    
    
    dist[start]=0;            //起点到自身的路径长度 
    
    for (i = 0; i < G.vernum - 1; i++)
    {
        int min_dist = MAX;
        int min_index;

        // 选择距离起点最近的未访问节点
        for (j = 0; j < G.vernum; j++)
        {
            if (visited[j] == false && dist[j] <= min_dist)
            {
                min_dist = dist[j];
                min_index = j;
            }
        }

        visited[min_index] = true;

        // 更新与该节点相邻节点的最短路径
        ArcNode *p = G.Ver[min_index].first->next;
        while (p)
        {
            int adjvex = p->adjvex;
            int weight = p->weight;
            if (visited[adjvex] == false && dist[min_index] != MAX 
                        && dist[min_index] + weight < dist[adjvex])
            {
                dist[adjvex] = dist[min_index] + weight;
            }
            p = p->next;
        }
    }

    // 打印最短路径结果
    printf("节点\t最短路径\n");
    for (i = 0; i < G.vernum; i++)
    {
        printf("%d\t%d\n", G.Ver[i].num, dist[i]);
    }
}

int main()
{
    Graph G;
    CreateGraph(G);
    printf("\n");
    displayGraph(G);
    printf("\n");
    dijkstra(G,0); 
    return 0;
}