以邻接表作存储结构实现求从源点到其余各顶点的最短路径的dijkstra算法代码

以下是以邻接表作存储结构实现Dijkstra算法的代码：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

// 邻接表存储图的边
struct Edge {
    int dest;   // 目标顶点
    int weight; // 权重
};

// 邻接表存储图的顶点
struct Vertex {
    int id;             // 顶点编号
    vector<Edge> edges; // 与该顶点相连的边
    int distance;       // 从源点到该顶点的最短距离
    bool visited;       // 是否已访问
};

// Dijkstra算法
void dijkstra(vector<Vertex>& graph, int source) {
    // 将源点到源点的距离设为0，其他顶点的距离设为无穷大
    for (int i = 0; i < graph.size(); i++) {
        graph[i].distance = INT_MAX;
        graph[i].visited = false;
    }
    graph[source].distance = 0;

    // 用小根堆保存未访问的顶点
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, source));

    while (!pq.empty()) {
        // 取出距离源点距离最近的顶点
        int u = pq.top().second;
        pq.pop();

        // 如果该顶点已访问，则继续下一轮循环
        if (graph[u].visited) {
            continue;
        }
        graph[u].visited = true;

        // 遍历该顶点的所有邻居
        for (int i = 0; i < graph[u].edges.size(); i++) {
            int v = graph[u].edges[i].dest;
            int weight = graph[u].edges[i].weight;

            // 如果从源点到邻居的距离更小，则更新距离
            if (graph[u].distance + weight < graph[v].distance) {
                graph[v].distance = graph[u].distance + weight;
                pq.push(make_pair(graph[v].distance, v));
            }
        }
    }
}

int main() {
    // 构建图
    vector<Vertex> graph(6);
    graph[0].id = 0;
    graph[0].edges.push_back({1, 6});
    graph[0].edges.push_back({2, 3});
    graph[1].id = 1;
    graph[1].edges.push_back({3, 5});
    graph[2].id = 2;
    graph[2].edges.push_back({1, 2});
    graph[2].edges.push_back({3, 3});
    graph[3].id = 3;
    graph[3].edges.push_back({4, 2});
    graph[3].edges.push_back({5, 3});
    graph[4].id = 4;
    graph[4].distance = INT_MAX;
    graph[5].id = 5;
    graph[5].distance = INT_MAX;

    // 运行Dijkstra算法
    dijkstra(graph, 0);

    // 输出结果
    for (int i = 0; i < graph.size(); i++) {
        cout << "Distance from source to vertex " << graph[i].id << ": " << graph[i].distance << endl;
    }

    return 0;
}

注：上述代码中小根堆使用了STL中的priority_queue，其默认是大根堆，需要传入参数greater<pair<int, int>>，表示使用小于运算符（即小根堆）。