C语言Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法，适合于寻找图中两点之间的最短路径。在C语言中应用Dijkstra算法来求解有向网G中从顶点v0到其他所有顶点的最短路径，需要遵循以下步骤：

1. 初始化：给每个节点赋初始距离无穷大（除了起点v0），将v0的距离设为0，将其标记为已访问。

2. 选择最小距离节点：从未访问节点中找到当前距离最小的节点u，并更新其相邻节点的距离，如果通过u可以到达更短的距离。

3. 标记节点：将u标记为已访问。

4. 重复步骤2和3，直到所有节点都被访问过，或者当前距离最小的节点已经是终点。

5. 最终结果：所有节点的距离数组就包含了从v0到各个节点的最短路径长度。

以下是简单的伪代码示例：

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

// 函数声明，使用优先队列（如二叉堆）存储节点及其距离
void dijkstra(int graph[][], int n, int src, int dist[], bool visited[], priority_queue<int> *pq);

// 主函数调用
int main() {
    int v0 = 0; // 指定起始顶点
    int graph[n][n]; // 图的邻接矩阵表示
    int dist[n], visited[n];
    
    dijkstra(graph, n, v0, dist, visited, &pq); // 调用Dijkstra算法

    // 输出最短路径
    for (int i = 1; i < n; ++i) {
        printf("The shortest path from %d to v0 is %d\n", i, dist[i]);
    }

    return 0;
}

// Dijkstra核心算法实现
void dijkstra(int graph[][n], int n, int src, int dist[], bool visited[], priority_queue<int> *pq) {
    // 初始化
    dist[src] = 0;
    pq->push(src);
    visited[src] = true;

    while (!pq->empty()) {
        int u = pq->top();
        pq->pop();

        // 更新未访问节点的距离
        for (int v = 0; v < n; ++v) {
            if (!visited[v] && graph[u][v] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                pq->push(v);
            }
        }
    }
}