最短路径dijkstra算法c++

Dijkstra算法是一种用于求解有向图或无向加权图中从起点到其他顶点最短路径的贪心算法。它通过维护一个优先级队列（通常使用二叉堆实现），逐步更新每个节点的距离，并选择距离当前已知最小的节点进行扩展。

以下是使用C++实现Dijkstra算法的基本步骤：

1. 初始化：设置起点的距离为0，其他所有节点的距离设为无穷大，标记为未访问。将起点加入优先队列。
2. 循环：从优先队列中取出距离最小的节点u。
3. 更新：对于u的所有邻居v，计算新的距离d(v) = d(u) + u到v的成本。如果这个新距离小于v当前的距离，则更新v的距离并将v加入优先队列。
4. 重复步骤2和3，直到优先队列为空，或者目标节点被访问过。

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

struct Node {
    int id;
    int distance;
    bool visited;

    Node(int id, int distance = std::numeric_limits<int>::max()) : id(id), distance(distance), visited(false) {}
};

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

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

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

        for (int neighbor : graph[current.id]) {
            Node neighborDist = distances[neighbor];
            if (!neighborDist.visited && current.distance + graph[current.id][neighbor] < neighborDist.distance) {
                neighborDist.distance = current.distance + graph[current.id][neighbor];
                neighborDist.visited = true;
                pq.push(neighborDist);
            }
        }
    }
}

// 使用示例
std::vector<int> graph = {{0, 4, 0}, {4, 0, 8}, {0, 8, 0}}; // 简化后的邻接矩阵表示
int start = 0;
std::vector<Node> distances(graph.size());
dijkstra(graph, start, distances);

// 输出最短路径（假设distances数组的索引对应于原图中的节点）
for (const auto& node : distances) {
    if (node.id != start) {
        std::cout << "Node " << node.id << " has shortest path from start with distance: " << node.distance << std::endl;
    }
}