迪杰斯克拉算法c++

Dijkstra算法是一种经典的最短路径算法，用于在加权图中找到两个顶点之间的最短路径。该算法基于贪心策略，每次选择当前距离起点最近的顶点，并更新从起点到其余顶点的距离值。

以下是Dijkstra算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

void dijkstra(vector<vector<pair<int, int>>> &graph, vector<int> &dist, int start) {
    int n = graph.size();
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

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

        for (auto &v : graph[u]) {
            if (dist[v.first] > dist[u] + v.second) {
                dist[v.first] = dist[u] + v.second;
                pq.push({dist[v.first], v.first});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> graph(n);
    vector<int> dist(n, INF);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w}); //无向图需要双向边
    }

    int start;
    cin >> start;

    dijkstra(graph, dist, start);

    for (int i = 0; i < n; i++) {
        cout << "Distance from " << start << " to " << i << " is " << dist[i] << endl;
    }

    return 0;
}