c++dijkstra算法

Dijkstra算法是一种用于解决单源最短路径问题的经典算法，它可以找到从一个顶点到其他所有顶点的最短路径。下面是C++中实现Dijkstra算法的基本步骤：

1. 创建一个距离数组dist[]，用于存储从源顶点到其他顶点的最短距离。初始化dist[]数组，将源顶点的距离设置为0，其他顶点的距离设置为无穷大。

2. 创建一个优先队列（最小堆）minHeap，用于选择下一个要访问的顶点。将源顶点加入minHeap，并将其距离设置为0。

3. 循环执行以下步骤，直到minHeap为空：
a. 从minHeap中取出距离最小的顶点u。
b. 遍历u的所有邻接顶点v，计算从源顶点到v的距离newDist。如果newDist小于dist[v]，则更新dist[v]为newDist，并将v加入minHeap。

4. 最终，dist[]数组中存储了从源顶点到所有其他顶点的最短距离。

下面是一个简单的C++代码示例：

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

using namespace std;

void dijkstra(vector<vector<pair<int, int>>>& graph, int source, vector<int>& dist) {
    int n = graph.size();
    dist.resize(n, INT_MAX);
    dist[source] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    minHeap.push({0, source});

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

        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            int newDist = dist[u] + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                minHeap.push({newDist, v});
            }
        }
    }
}

int main() {
    int n = 5; // 顶点数
    vector<vector<pair<int, int>>> graph(n);

    // 添加边
    graph[0].push_back({1, 2});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 7});
    graph[2].push_back({3, 3});
    graph[2].push_back({4, 5});
    graph[3].push_back({4, 2});

    int source = 0; // 源顶点

    vector<int> dist;
    dijkstra(graph, source, dist);

    // 输出最短路径
    for (int i = 0; i < n; i++) {
        cout << "Distance from source to vertex " << i << ": " << dist[i] << endl;
    }

    return 0;
}