dijkstra算法邻接表c语言代码

下面是使用邻接表实现Dijkstra算法的C语言代码：

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

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

// 边的结构体
typedef struct Edge {
    int dest; // 目标顶点编号
    int weight; // 权重
    struct Edge *next; // 下一条边指针
} Edge;

// 邻接表中顶点的结构体
typedef struct Vertex {
    Edge *head; // 第一条边
} Vertex;

// 图的结构体
typedef struct Graph {
    Vertex vertices[MAX_VERTEX_NUM]; // 顶点数组
    int vertex_num; // 顶点数
} Graph;

// 初始化图
void init_graph(Graph *graph, int vertex_num) {
    graph->vertex_num = vertex_num;
    for (int i = 0; i < vertex_num; i++) {
        graph->vertices[i].head = NULL;
    }
}

// 添加边
void add_edge(Graph *graph, int src, int dest, int weight) {
    Edge *edge = (Edge *) malloc(sizeof(Edge));
    edge->dest = dest;
    edge->weight = weight;
    edge->next = graph->vertices[src].head;
    graph->vertices[src].head = edge;
}

// Dijkstra算法
void dijkstra(Graph *graph, int start, int *dist, int *prev) {
    int visited[MAX_VERTEX_NUM] = {0}; // 是否已经访问
    for (int i = 0; i < graph->vertex_num; i++) {
        dist[i] = INF; // 到各个顶点的距离都设置为无穷大
        prev[i] = -1; // 各个顶点的前驱顶点都设置为-1
    }
    dist[start] = 0; // 起点到自身的距离为0
    for (int i = 0; i < graph->vertex_num; i++) {
        int min_dist = INF;
        int u = -1;
        // 找到未访问顶点中距离最近的顶点
        for (int j = 0; j < graph->vertex_num; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        if (u == -1) {
            break;
        }
        visited[u] = 1; // 标记为已访问
        // 更新与顶点u相邻的顶点的距离
        for (Edge *edge = graph->vertices[u].head; edge != NULL; edge = edge->next) {
            int v = edge->dest;
            int w = edge->weight;
            if (!visited[v] && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;
            }
        }
    }
}

// 打印最短路径
void print_path(Graph *graph, int start, int end, int *prev) {
    if (start == end) {
        printf("%d", start);
    } else if (prev[end] == -1) {
        printf("无路径");
    } else {
        print_path(graph, start, prev[end], prev);
        printf("->%d", end);
    }
}

int main() {
    Graph graph;
    init_graph(&graph, 5);
    add_edge(&graph, 0, 1, 10);
    add_edge(&graph, 0, 3, 30);
    add_edge(&graph, 0, 4, 100);
    add_edge(&graph, 1, 2, 50);
    add_edge(&graph, 2, 4, 10);
    add_edge(&graph, 3, 2, 20);
    add_edge(&graph, 3, 4, 60);
    int dist[MAX_VERTEX_NUM];
    int prev[MAX_VERTEX_NUM];
    dijkstra(&graph, 0, dist, prev);
    for (int i = 1; i < graph.vertex_num; i++) {
        printf("0到%d的最短距离为%d，路径为", i, dist[i]);
        print_path(&graph, 0, i, prev);
        printf("\n");
    }
    return 0;
}

该代码使用邻接表存储图，实现了Dijkstra算法，可以求解任意两个顶点之间的最短路径。