用C++写Dijkstra算法

以下是用C++实现Dijkstra算法的示例代码：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

#define INF INT_MAX

// 邻接表存储图
struct Edge {
    int to; // 目标节点
    int weight; // 边权重
    Edge(int t, int w) : to(t), weight(w) {}
};

typedef vector<vector<Edge>> Graph;

vector<int> dijkstra(const Graph& g, int s) {
    int n = g.size();
    vector<int> dist(n, INF); // 存储源节点到各个节点的最短距离
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆
    dist[s] = 0;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (auto& e : g[u]) {
            int v = e.to;
            int w = e.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    return dist;
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(Edge(v, w));
        g[v].push_back(Edge(u, w)); // 无向图
    }
    vector<int> dist = dijkstra(g, s);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            cout << "INF" << endl;
        } else {
            cout << dist[i] << endl;
        }
    }
    return 0;
}

该程序首先定义了一个结构体Edge，用于存储边信息。接着定义了一个邻接表类型Graph，用于存储图的信息。dijkstra函数是实现Dijkstra算法的核心函数，它接受一个邻接表和源节点s，返回一个vector类型的数组，存储源节点到各个节点的最短距离。在函数内部，我们首先初始化距离数组dist，将源节点到各个节点的距离初始化为INF，然后初始化一个小根堆pq，将源节点入队。接着进入主循环，每次从小根堆中取出距离源节点最近的节点u，然后遍历u的所有邻居节点v，更新v的距离，如果距离被更新，则将v入队。最后返回距离数组dist。

在main函数中，我们首先读入图的信息，然后调用dijkstra函数，得到源节点到各个节点的最短距离。最后输出距离数组dist，如果某个节点的距离为INF，则输出"INF"。