dijkstra C语言实现

Dijkstra算法是一种用于解决单源最短路径问题的经典算法。该算法可以在带权重的有向图中找到从起点到其他所有节点的最短路径。下面是Dijkstra算法在C语言中的实现。

引用[3]中给出了一个邻接矩阵的实现，下面是一个基于邻接表的实现：

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

#define MAX_VERTICES 100

typedef struct Edge {
    int dest;
    int weight;
    struct Edge* next;
} Edge;

typedef struct Vertex {
    int id;
    int dist;
    Edge* edges;
} Vertex;

typedef struct Graph {
    Vertex vertices[MAX_VERTICES];
    int num_vertices;
} Graph;

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].edges;
    graph->vertices[src].edges = edge;
}

void dijkstra(Graph* graph, int start) {
    int visited[MAX_VERTICES] = {0};
    for (int i = 0; i < graph->num_vertices; i++) {
        graph->vertices[i].dist = INT_MAX;
    }
    graph->vertices[start].dist = 0;
    for (int i = 0; i < graph->num_vertices; i++) {
        int min_dist = INT_MAX;
        int min_vertex = -1;
        for (int j = 0; j < graph->num_vertices; j++) {
            if (!visited[j] && graph->vertices[j].dist < min_dist) {
                min_dist = graph->vertices[j].dist;
                min_vertex = j;
            }
        }
        if (min_vertex == -1) {
            break;
        }
        visited[min_vertex] = 1;        Edge* edge = graph->vertices[min_vertex].edges;
        while (edge != NULL) {
            int dest = edge->dest;            int weight = edge->weight;
            if (!visited[dest] && graph->vertices[min_vertex].dist + weight < graph->vertices[dest].dist) {
                graph->vertices[dest].dist = graph->vertices[min_vertex].dist + weight;
            }
            edge = edge->next;
        }
    }
}

int main() {
    Graph graph;
    graph.num_vertices = 5;
    for (int i = 0; i < graph.num_vertices; i++) {
        graph.vertices[i].id = i;
        graph.vertices[i].edges = NULL;
    }
    add_edge(&graph, 0, 1, 10);
    add_edge(&graph, 0, 4, 5);
    add_edge(&graph, 1, 2, 1);
    add_edge(&graph, 1, 4, 2);
    add_edge(&graph, 2, 3, 4);
    add_edge(&graph, 3, 2, 6);
    add_edge(&graph, 3, 0, 7);
    add_edge(&graph, 4, 1, 3);
    add_edge(&graph, 4, 2, 9);
    add_edge(&graph, 4, 3, 2);
    dijkstra(&graph, 0);
    for (int i = 0; i < graph.num_vertices; i++) {
        printf("Shortest distance from vertex 0 to vertex %d is %d\n", i, graph.vertices[i].dist);
    }
    return 0;
}

这个实现使用了邻接表来表示图，使用了一个visited数组来记录哪些节点已经被访问过，使用了一个dist数组来记录每个节点到起点的最短距离。在每次循环中，找到未访问过的dist最小的节点，将其标记为已访问，然后更新与该节点相邻的节点的dist值。