DijkstraC++实现

Dijkstra算法是一种用于寻找图中两个节点之间最短路径的经典算法。在C++中实现Dijkstra算法，通常会采用优先队列数据结构来存储待处理的节点，并维护每个节点的当前距离。以下是简单的步骤概述：

1. 初始化：设置起点的距离为0，其他所有节点的距离为无穷大。将起点加入到优先队列中。

2. 优先级队列操作：从队列中取出距离最小的节点（通常使用最小堆），然后更新与其相邻节点的距离，如果通过这个节点可以到达更小的距离，就更新它们的距离并重新插入队列。

3. 检查终止条件：当队列为空，或者找到终点时，算法结束。此时，终点的最后更新距离即是最短路径长度。

4. 路径跟踪：记录下每一步的选择，以便重建最短路径。

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

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

struct Node {
    int distance;
    int vertex;
    Node(int dist, int vert) : distance(dist), vertex(vert) {}
};

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

void dijkstra(std::vector<std::vector<int>>& adjList, int start, std::vector<int>& distances, std::vector<bool>& visited) {
    distances[start] = 0;
    std::priority_queue<Node, std::vector<Node>, decltype(compareNodes)> pq(compareNodes);
    pq.push({0, start});

    while (!pq.empty()) {
        Node current = pq.top(); // 取出当前最短距离的节点
        pq.pop();
        
        if (visited[current.vertex]) continue; // 如果已访问过，跳过

        visited[current.vertex] = true;

        for (int neighbor : adjList[current.vertex]) {
            int altDistance = current.distance + adjList[current.vertex][neighbor];
            if (altDistance < distances[neighbor]) {
                distances[neighbor] = altDistance;
                pq.push({altDistance, neighbor});
            }
        }
    }
}