c++实现迪杰斯特拉算法

Dijkstra算法是一种最短路径算法，用于在加权图中找到从起点到终点的最短路径。以下是C++实现Dijkstra算法的基本步骤：

1. 创建一个源到所有其他节点的距离数组dist[]并将其初始化为无穷大。

2. 将源节点的距离设置为0，并将其插入到一个最小优先队列中。

3. 从队列中取出最小节点v，并遍历其所有邻居节点w。

4. 对于每个邻居节点w，如果从源节点到该邻居节点的距离比当前已知的距离短，则更新dist[]数组并将其插入到队列中。

5. 重复步骤3和步骤4，直到队列为空。

6. dist[]数组中存储了源节点到所有其他节点的最短路径。

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

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

using namespace std;

typedef pair<int, int> pii;

const int INF = INT_MAX;

vector<vector<pii>> adj;

vector<int> dijkstra(int start, int n) {
    vector<int> dist(n, INF);
    dist[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (auto v : adj[u]) {
            int weight = v.second;
            if (dist[v.first] > dist[u] + weight) {
                dist[v.first] = dist[u] + weight;
                pq.push(make_pair(dist[v.first], v.first));
            }
        }
    }
    return dist;
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
    int start;
    cin >> start;
    vector<int> dist = dijkstra(start, n);
    for (int i = 0; i < n; ++i) {
        cout << "Distance from " << start << " to " << i << " is " << dist[i] << endl;
    }
    return 0;
}