C++实现Dijkstra算法

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

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

#define INF INT_MAX // 定义无穷大

// 定义边的结构体
struct Edge {
    int to; // 边的终点
    int cost; // 边的权值
};

// 定义图的结构体
struct Graph {
    int V; // 图的顶点数
    vector<vector<Edge>> adj; // 邻接表
};

// Dijkstra算法
vector<int> dijkstra(const Graph& g, int s) {
    vector<int> dist(g.V, INF); // 存储起点到各点的最短距离
    dist[s] = 0; // 起点到自己的距离为0

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    // 存储已经确定最短路的节点
    vector<bool> used(g.V, false);
    que.push(make_pair(0, s));

    while (!que.empty()) {
        pair<int, int> p = que.top();
        que.pop();
        int v = p.second;
        if (used[v]) {
            continue;
        }
        used[v] = true;
        for (auto& e : g.adj[v]) {
            if (dist[e.to] > dist[v] + e.cost) {
                dist[e.to] = dist[v] + e.cost;
                que.push(make_pair(dist[e.to], e.to));
            }
        }
    }

    return dist;
}

int main() {
    // 用邻接表表示下面这个图
    //     1
    //  7 / \3
    //   /   \
    //  0-----2
    //  5\   /2
    //    \ /
    //     3
    Graph g = { 4, vector<vector<Edge>>(4) };
    g.adj[0].push_back(Edge{ 1, 7 });
    g.adj[0].push_back(Edge{ 3, 5 });
    g.adj[1].push_back(Edge{ 0, 7 });
    g.adj[1].push_back(Edge{ 2, 3 });
    g.adj[2].push_back(Edge{ 0, 3 });
    g.adj[2].push_back(Edge{ 1, 3 });
    g.adj[2].push_back(Edge{ 3, 2 });
    g.adj[3].push_back(Edge{ 0, 5 });
    g.adj[3].push_back(Edge{ 2, 2 });

    vector<int> dist = dijkstra(g, 0);
    for (int i = 0; i < dist.size(); i++) {
        cout << "0 -> " << i << ": " << dist[i] << endl;
    }

    return 0;
}

注释已经很详细了，这里简单解释一下。首先定义了边的结构体和图的结构体，存储边和邻接表。然后是Dijkstra算法的实现，使用了优先队列来存储已经确定最短路的节点，每次取出队列中距离起点最近的点进行扩展，如果扩展后可以更新到达其它点的距离，则更新距离。最后返回起点到各点的最短距离。最后在main函数中构造了一个图来测试Dijkstra算法的正确性。