dijkstra算法代码c++

Dijkstra算法是一种用于寻找图中两点之间最短路径的贪心算法。在C++中，我们可以使用优先队列（如`std::priority_queue`）来实现。以下是一个简单的Dijkstra算法的C++代码示例：

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

struct Edge {
    int to, weight;
};

struct Node {
    int id, dist = INT_MAX; // 初始距离设为无穷大
    bool visited = false;

    bool operator<(const Node& other) const { return dist < other.dist; }
};

void dijkstra(std::vector<Edge>& edges, std::vector<int>& graph, int start) {
    int numVertices = graph.size();
    std::priority_queue<Node> pq;
    pq.push({start, 0}); // 将起始节点加入队列，距离为0

    while (!pq.empty()) {
        Node current = pq.top(); // 取出距离最小的节点
        pq.pop();

        if (current.visited) continue; // 如果已访问过，跳过

        current.visited = true;

        for (Edge edge : edges[current.id]) {
            int newDist = current.dist + edge.weight;
            if (newDist < graph[edge.to]) {
                graph[edge.to] = newDist;
                pq.push({edge.to, newDist});
            }
        }
    }
}

int main() {
    std::vector<Edge> edges = {{0, 1}, {1, 2}, {0, 7}, {1, 6}, {2, 5}, {3, 1}, {3, 8}, {4, 3}};
    std::vector<int> graph(edges.size(), INT_MAX); // 初始化图中的所有边为无穷大

    dijkstra(edges, graph, 0); // 从节点0开始搜索

    for (int i = 0; i < graph.size(); ++i) {
        if (graph[i] == INT_MAX) {
            std::cout << "No path found to node " << i << std::endl;
        } else {
            std::cout << "Shortest distance from node 0 to node " << i << " is: " << graph[i] << std::endl;
        }
    }

    return 0;
}

在这个代码中，`edges`是一个边的集合，`graph`是一个表示图的邻接矩阵或邻接列表，`start`是起点。算法首先将起始节点加入优先队列，然后不断取出队列中距离最小的节点，更新与其相连的边的终点的最短距离，并重新调整优先级队列。直到队列为空，遍历结束。