C语言dijkstra

Dijkstra算法是一种用来解决最短路径问题的贪心算法。在C语言中，实现Dijkstra算法需要以下步骤：

1. 定义一个数组dist，用来存储起点到每个节点的最短距离。初始时，将起点到自己的距离设置为0，其余节点的距离设置为无穷大。

2. 定义一个数组visited，用来记录每个节点是否已经访问过。初始时，将起点设置为已访问。

3. 从起点开始，遍历所有的邻居节点，更新其到起点的最短距离。如果更新后的距离比原来的距离短，则将其加入到一个优先队列中。

4. 从优先队列中取出距离起点最短的节点，将其标记为已访问，并重复步骤3，直到所有节点都被访问过。

以下是一个简单的C语言实现：

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

#define MAX_NODES 1000

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

typedef struct {
    EdgeNode* head;
} AdjList[MAX_NODES];

typedef struct {
    int dist;
    int prev;
    int visited;
    AdjList adj_list;
} Graph;

void add_edge(Graph* graph, int src, int dest, int weight) {
    EdgeNode* new_node = (EdgeNode*) malloc(sizeof(EdgeNode));
    new_node->dest = dest;
    new_node->weight = weight;
    new_node->next = graph->adj_list[src].head;
    graph->adj_list[src].head = new_node;
}

void dijkstra(Graph* graph, int start) {
    int dist[MAX_NODES];
    int visited[MAX_NODES];
    int prev[MAX_NODES];
    int i, j;

    for (i = 0; i < MAX_NODES; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
        prev[i] = -1;
    }

    dist[start] = 0;

    for (i = 0; i < MAX_NODES; i++) {
        int min_dist = INT_MAX;
        int min_node = -1;

        for (j = 0; j < MAX_NODES; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_node = j;
            }
        }

        if (min_node == -1) {
            break;
        }

        visited[min_node] = 1;

        EdgeNode* edge = graph->adj_list[min_node].head;

        while (edge != NULL) {
            int dest = edge->dest;
            int weight = edge->weight;

            if (dist[min_node] + weight < dist[dest]) {
                dist[dest] = dist[min_node] + weight;
                prev[dest] = min_node;
            }

            edge = edge->next;
        }
    }

    printf("Shortest distances from node %d:\n", start);

    for (i = 0; i < MAX_NODES; i++) {
        printf("Node %d: %d\n", i, dist[i]);
    }
}

int main() {
    Graph graph;
    int i, j;

    for (i = 0; i < MAX_NODES; i++) {
        graph.adj_list[i].head = NULL;
    }

    add_edge(&graph, 0, 1, 4);
    add_edge(&graph, 0, 7, 8);
    add_edge(&graph, 1, 0, 4);
    add_edge(&graph, 1, 7, 11);
    add_edge(&graph, 1, 2, 8);
    add_edge(&graph, 2, 1, 8);
    add_edge(&graph, 2, 3, 7);
    add_edge(&graph, 2, 5, 4);
    add_edge(&graph, 2, 8, 2);
    add_edge(&graph, 3, 2, 7);
    add_edge(&graph, 3, 4, 9);
    add_edge(&graph, 3, 5, 14);
    add_edge(&graph, 4, 3, 9);
    add_edge(&graph, 4, 5, 10);
    add_edge(&graph, 5, 2, 4);
    add_edge(&graph, 5, 3, 14);
    add_edge(&graph, 5, 4, 10);
    add_edge(&graph, 5, 6, 2);
    add_edge(&graph, 6, 5, 2);
    add_edge(&graph, 6, 7, 1);
    add_edge(&graph, 6, 8, 6);
    add_edge(&graph, 7, 0, 8);
    add_edge(&graph, 7, 1, 11);
    add_edge(&graph, 7, 6, 1);
    add_edge(&graph, 7, 8, 7);
    add_edge(&graph, 8, 2, 2);
    add_edge(&graph, 8, 6, 6);
    add_edge(&graph, 8, 7, 7);

    dijkstra(&graph, 0);

    return 0;
}

该程序使用邻接链表来表示图，实现了Dijkstra算法来计算从起点0到其他节点的最短距离。