Dijkstra算法 C++

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法，通常应用于图论中的带权重的无向或有向图中。在C++中，你可以通过以下几个步骤实现Dijkstra算法：

1. **初始化**：创建一个优先队列（如`std::priority_queue`），其中包含所有节点，初始距离设为无穷大，起点的距离设为0。

2. **选择最小距离节点**：从优先队列中取出距离最小的节点。

3. **更新邻接节点**：对于当前节点的所有未访问邻居，计算它们到起点的距离（即当前节点距离加上边的权重），如果这个新距离小于之前的距离，则更新该节点的距离，并将其加入队列。

4. **检查结束条件**：如果优先队列为空或者当前节点是最远点，则算法结束；否则，返回到步骤2。

5. **存储结果**：在算法结束时，记录下每个节点到达起点的最短距离和最近的前驱节点，用于重建最短路径。

下面是一个简单的C++模板示例：

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

using namespace std;

struct Node {
    int id;
    int distance;
    Node* previous;
};

bool compareNodes(Node a, Node b) { return a.distance < b.distance; }

void dijkstra(vector<vector<int>>& graph, int start) {
    int numVertices = graph.size();
    vector<Node> nodes(numVertices);
    
    for (int i = 0; i < numVertices; ++i)
        nodes[i].distance = numeric_limits<int>::max();

    nodes[start].distance = 0;
    priority_queue<Node, vector<Node>, decltype(compareNodes)> pq(compareNodes);

    for (Node& node : nodes)
        pq.push(node);

    while (!pq.empty()) {
        Node current = pq.top(); pq.pop();
        if (current.id == start) break;

        for (int neighbor : graph[current.id]) {
            int altDistance = current.distance + graph[current.id][neighbor];
            if (altDistance < nodes[neighbor].distance) {
                nodes[neighbor].distance = altDistance;
                nodes[neighbor].previous = &current;
                pq.push(nodes[neighbor]);
            }
        }
    }

    // 输出或处理结果...
}

int main() {
    // 示例图的结构...
    // 调用dijkstra函数并传入起始节点
    dijkstra(graph, start);
    // 结果分析和展示...
    return 0;
}