迪杰斯特拉算法代码c++

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

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

using namespace std;

const int INF = INT_MAX; // 无穷大

// 边的结构体
struct Edge {
    int to; // 目标节点
    int weight; // 权重
};

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

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    // 添加边
    void addEdge(int u, int v, int weight) {
        Edge edge;
        edge.to = v;
        edge.weight = weight;
        adj[u].push_back(edge);
    }

    // Dijkstra算法
    vector<int> dijkstra(int start) {
        vector<int> dist(V, INF); // 存储最短距离
        dist[start] = 0; // 起始节点到自身的距离为0

        // 创建优先队列，按照距离从小到大排序
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push(make_pair(0, start));

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            // 遍历u的所有邻接节点
            for (const Edge& edge : adj[u]) {
                int v = edge.to;
                int weight = edge.weight;

                // 如果经过u到v的距离更短，则更新最短距离
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }

        return dist;
    }
};

int main() {
    int V, E;
    cin >> V >> E; // 输入节点数和边数

    Graph graph(V);

    // 输入边的信息
    for (int i = 0; i < E; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph.addEdge(u, v, weight);
    }

    int start;
    cin >> start; // 输入起始节点

    vector<int> dist = graph.dijkstra(start); // 调用Dijkstra算法

    // 输出最短距离
    for (int i = 0; i < V; i++) {
        cout << "最短距离[" << start << "][" << i << "] = " << dist[i] << endl;
    }

    return 0;
}