以邻接表作存储结构实现求从源点到其余各顶点的最短路径的 Dijkstra算法。c语言实现

以下是基于邻接表实现的Dijkstra算法的c语言代码：

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

#define MAX_VERTEX_NUM 100 //最大顶点数
#define INF INT_MAX //表示正无穷

typedef struct ArcNode{
    int adjvex;          //该弧所指向的顶点的位置
    int weight;          //该弧的权值
    struct ArcNode *nextarc;  //指向下一条弧的指针
}ArcNode;

typedef struct VNode{
    int data;            //顶点的数据
    ArcNode *firstarc;   //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList vertices;   //邻接表
    int vexnum, arcnum; //图的当前顶点数和弧数
}ALGraph;

void CreateGraph(ALGraph *G){
    int i, j, w;
    ArcNode *p;
    printf("请输入顶点数和弧数：\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入%d个顶点的值：\n", G->vexnum);
    for(i = 0; i < G->vexnum; i++){
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    printf("请输入%d条弧的起点、终点和权值：\n", G->arcnum);
    for(i = 0; i < G->arcnum; i++){
        scanf("%d%d%d", &i, &j, &w);
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = w;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->weight = w;
        p->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p;
    }
}

void Dijkstra(ALGraph G, int start, int *dist, int *path){
    bool visited[MAX_VERTEX_NUM] = {false};   //用于记录顶点是否被访问过的数组
    int i, j, k, min;
    ArcNode *p;
    //初始化dist数组和path数组
    for(i = 0; i < G.vexnum; i++){
        dist[i] = INF;
        path[i] = -1;
    }
    visited[start] = true;
    dist[start] = 0;
    //更新dist数组和path数组
    for(i = 0; i < G.vexnum-1; i++){
        min = INF;
        for(j = 0; j < G.vexnum; j++){
            if(!visited[j] && dist[j] < min){
                k = j;
                min = dist[j];
            }
        }
        visited[k] = true;
        for(p = G.vertices[k].firstarc; p; p = p->nextarc){
            if(!visited[p->adjvex] && dist[k] + p->weight < dist[p->adjvex]){
                dist[p->adjvex] = dist[k] + p->weight;
                path[p->adjvex] = k;
            }
        }
    }
}

int main(){
    ALGraph G;
    CreateGraph(&G);
    int start;
    printf("请输入起点的位置：\n");
    scanf("%d", &start);
    int dist[MAX_VERTEX_NUM], path[MAX_VERTEX_NUM];
    Dijkstra(G, start, dist, path);
    int i;
    printf("起点到各顶点的最短路径长度如下：\n");
    for(i = 0; i < G.vexnum; i++){
        printf("%d ", dist[i]);
    }
    printf("\n起点到各顶点的最短路径如下：\n");
    for(i = 0; i < G.vexnum; i++){
        printf("%d ", i);
        int j = i;
        while(path[j] != -1){
            printf("<--%d", path[j]);
            j = path[j];
        }
        printf("\n");
    }
    return 0;
}

该算法先通过CreateGraph函数创建邻接表存储的图，然后通过Dijkstra函数求出从起点start到其他各顶点的最短路径长度和最短路径。在求解过程中，使用visited数组记录每个顶点是否被访问过，使用dist数组记录起点到每个顶点的最短路径长度，使用path数组记录起点到每个顶点的最短路径上的前驱顶点。在算法开始时，将起点的dist值设为0，将起点标记为已访问过。然后，依次遍历每个未访问过的顶点，找出dist值最小的顶点，将其标记为已访问过，并更新其相邻顶点的dist值和path值。最后，输出起点到各顶点的最短路径长度和最短路径。