dijkstra算法C实现

Dijkstra算法是一种用于寻找图中两点之间最短路径的贪心算法。在C语言中实现Dijkstra算法通常涉及以下几个步骤：

1. **初始化**：创建一个优先队列（如最小堆），将所有节点的距离设置为无穷大，起点的距离设为0。

2. **标记过程**：从起点开始，将起点加入队列。对于每个节点u，更新其相邻节点v的距离，如果通过u到达v的距离小于已知距离，则更新v的距离，并将v添加到队列中。

3. **选择最小边**：从队列中取出当前距离起点最近的节点u。

4. **检查未访问节点**：对u的所有邻居v，如果通过u到达v的距离小于v之前的最短距离，更新v的距离，并在队列中调整v的位置。

5. **重复直到终点**：重复上述步骤，直到队列为空或者找到目标节点。若队列空而未达到目标，说明图中存在负权边，算法无法得出正确的结果。

以下是简单的C代码片段示例（假设`graph[]`是一个邻接矩阵表示的图，`dist[]`存储当前节点距离起点的距离，`visited[]`记录节点是否已被访问）：

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

// 边结构体
typedef struct {
    int src, dest, weight;
} Edge;

void dijkstra(int start, int graph[][V], int dist[], int V) {
    // 初始化
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[start] = 0;
    
    // 优先队列操作
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = 1;
        
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                pq.push({dist[v], v});
            }
        }
    }
}

// 使用示例
#define V 9
int main() {
    int graph[V][V] = {/* 图的邻接矩阵 */};
    int dist[V] = {0};
    dijkstra(0, graph, dist, V);
    printf("Shortest distance from node 0 to all other nodes:\n");
    for (int i = 0; i < V; i++) {
        printf("%d -> %d\n", i, dist[i]);
    }
    return 0;
}