Dijkstra算法求解最短路径的C语言

Dijkstra算法是一种用于解决带权图的单源最短路径问题的贪心算法。下面是Dijkstra算法求解最短路径的C语言实现：

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

#define MAX_VERTICES 1000

typedef struct {
    int vertex;
    int weight;
} Edge;

typedef struct {
    Edge edges[MAX_VERTICES][MAX_VERTICES];
    int n_vertices;
    int n_edges;
} Graph;

void add_edge(Graph *graph, int u, int v, int weight) {
    graph->edges[u][v].vertex = v;
    graph->edges[u][v].weight = weight;
}

void dijkstra(Graph *graph, int start, int *dist, int *prev) {
    int visited[MAX_VERTICES] = {0};
    int i, j, k, min_dist, next_vertex;

    for (i = 0; i < graph->n_vertices; i++) {
        dist[i] = INT_MAX;
        prev[i] = -1;
    }

    dist[start] = 0;

    for (i = 0; i < graph->n_vertices; i++) {
        min_dist = INT_MAX;
        for (j = 0; j < graph->n_vertices; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                next_vertex = j;
            }
        }

        visited[next_vertex] = 1;

        for (k = 0; k < graph->n_vertices; k++) {
            if (graph->edges[next_vertex][k].weight != 0) {
                int new_dist = dist[next_vertex] + graph->edges[next_vertex][k].weight;
                if (new_dist < dist[k]) {
                    dist[k] = new_dist;                    prev[k] = next_vertex;
                }
            }
        }
    }
}

int main() {
    Graph graph;
    int dist[MAX_VERTICES], prev[MAX_VERTICES];
    int i, j;

    graph.n_vertices = 5;
    graph.n_edges = 7;

    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);

    dijkstra(&graph, 0, dist, prev);

    for (i = 0; i < graph.n_vertices; i++) {
        printf("Vertex %d, Distance: %d, Previous Vertex: %d\n", i, dist[i], prev[i]);
    }

    return 0;
}

该实现使用邻接矩阵来表示图，并使用dist和prev数组来存储每个顶点的最短距离和前驱顶点。在dijkstra函数中，首先初始化dist和prev数组，然后遍历所有顶点，找到当前未访问的顶点中距离起点最近的顶点，将其标记为已访问，并更新与其相邻的顶点的最短距离和前驱顶点。最后，输出每个顶点的最短距离和前驱顶点。