最短路径dijkstra算法 c++

以下是使用C++实现Dijkstra算法求解最短路径的示例代码：

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

using namespace std;

// 定义边的结构体
struct Edge {
    int to; // 边的终点
    int weight; // 边的权重
    Edge(int t, int w) : to(t), weight(w) {}
};

// 定义图的结构体
struct Graph {
    int V; // 图的顶点数
    vector<vector<Edge>> adj; // 邻接表表示的图
    Graph(int v) : V(v), adj(v) {}
    void addEdge(int u, int v, int w) { // 添加一条边
        adj[u].push_back(Edge(v, w));
        adj[v].push_back(Edge(u, w));
    }
};

// Dijkstra算法求解最短路径
vector<int> dijkstra(const Graph& G, int s) {
    vector<int> dist(G.V, INT_MAX); // 存储起点到各个顶点的最短距离
    dist[s] = 0; // 起点到自身的距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆
    pq.push(make_pair(0, s)); // 将起点加入小根堆
    while (!pq.empty()) {
        int u = pq.top().second; // 取出小根堆中距离最小的顶点
        pq.pop();
        for (auto& e : G.adj[u]) { // 遍历u的所有邻接点
            int v = e.to;
            int w = e.weight;
            if (dist[v] > dist[u] + w) { // 如果通过u可以使v到起点的距离更短
                dist[v] = dist[u] + w; // 更新v到起点的最短距离
                pq.push(make_pair(dist[v], v)); // 将v加入小根堆
            }
        }
    }
    return dist;
}

// 示例
int main() {
    Graph G(5); // 创建一个5个顶点的图
    G.addEdge(0, 1, 10); // 添加边
    G.addEdge(0, 4, 5);
    G.addEdge(1, 2, 1);
    G.addEdge(1, 4, 2);
    G.addEdge(2, 3, 4);
    G.addEdge(3, 2, 6);
    G.addEdge(3, 0, 7);
    G.addEdge(4, 1, 3);
    G.addEdge(4, 2, 9);
    G.addEdge(4, 3, 2);
    vector<int> dist = dijkstra(G, 0); // 求解起点为0的最短路径
    for (int i = 0; i < G.V; i++) {
        cout << "0到" << i << "的最短距离为：" << dist[i] << endl;
    }
    return 0;
}