用C语言实现dijkstra算法

Dijkstra算法是一种经典的最短路径算法，用于在加权图中寻找单源最短路径。下面是C语言实现Dijkstra算法的示例代码：

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

#define MAX_VERTICES 1000

typedef struct Graph {
    int num_vertices;
    int matrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

Graph* create_graph(int num_vertices) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            graph->matrix[i][j] = 0;
        }
    }
    return graph;
}

void add_edge(Graph* graph, int src, int dst, int weight) {
    graph->matrix[src][dst] = weight;
}

int get_min_distance(int* distances, bool* visited, int num_vertices) {
    int min_distance = INT_MAX;
    int min_index = -1;
    for (int i = 0; i < num_vertices; i++) {
        if (!visited[i] && distances[i] <= min_distance) {
            min_distance = distances[i];
            min_index = i;
        }
    }
    return min_index;
}

void dijkstra(Graph* graph, int src, int* distances) {
    bool visited[MAX_VERTICES] = { false };
    for (int i = 0; i < graph->num_vertices; i++) {
        distances[i] = INT_MAX;
    }
    distances[src] = 0;
    for (int i = 0; i < graph->num_vertices - 1; i++) {
        int u = get_min_distance(distances, visited, graph->num_vertices);
        visited[u] = true;
        for (int v = 0; v < graph->num_vertices; v++) {
            if (!visited[v] && graph->matrix[u][v] && distances[u] != INT_MAX && distances[u] + graph->matrix[u][v] < distances[v]) {
                distances[v] = distances[u] + graph->matrix[u][v];
            }
        }
    }
}

int main() {
    int num_vertices;
    scanf("%d", &num_vertices);
    Graph* graph = create_graph(num_vertices);
    int num_edges;
    scanf("%d", &num_edges);
    for (int i = 0; i < num_edges; i++) {
        int src, dst, weight;
        scanf("%d %d %d", &src, &dst, &weight);
        add_edge(graph, src, dst, weight);
    }
    int src;
    scanf("%d", &src);
    int distances[MAX_VERTICES];
    dijkstra(graph, src, distances);
    for (int i = 0; i < num_vertices; i++) {
        printf("Shortest distance from %d to %d is %d\n", src, i, distances[i]);
    }
    return 0;
}

输入格式为：

<num_vertices>
<num_edges>
<src> <dst> <weight>
...

其中 `<num_vertices>` 表示图中的顶点数， `<num_edges>` 表示边数，每行输入一个边，包括源顶点、目标顶点和权重。最后一行输入源顶点。输出为源顶点到所有顶点的最短距离。