邻接表储存结构下实现Dijkstra算法

Dijkstra算法是一种解决单源最短路径问题的贪心算法。在邻接表储存结构下实现Dijkstra算法，可以按照以下步骤进行：

1. 初始化：将源点与其它所有点的距离初始化为无穷大，源点的距离为0。

2. 选点：从未确定最短路径的点中选一个距离最小的点，作为当前确定的最短路径点。

3. 松弛：对当前确定的最短路径点的所有出边进行松弛操作，如果有更短的路径，则更新该点到源点的距离。

4. 重复：重复第2、3步，直到所有点都被确定了最短路径。

下面是邻接表储存结构下实现Dijkstra算法的代码示例：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int to;
    int w;
};

vector<Edge> G[100]; // 邻接表
int d[100];          // d[i]表示从源点到i点的最短距离

void dijkstra(int s) {  // s为源点
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆
    pq.push(make_pair(0, s)); // 将源点加入堆中
    d[s] = 0; // 初始化源点到自身的距离为0

    while (!pq.empty()) {
        pair<int, int> p = pq.top(); // 取出堆中距离最小的点
        pq.pop();
        int v = p.second; // 当前距离最小的点
        if (d[v] < p.first) continue; // 如果当前点的距离已经大于最小距离，则不需要再进行松弛操作

        // 遍历当前点的出边
        for (int i = 0; i < G[v].size(); i++) {
            Edge e = G[v][i];
            if (d[e.to] > d[v] + e.w) { // 如果从源点到e.to的距离大于从源点到v的距离加上v到e.to的距离
                d[e.to] = d[v] + e.w; // 更新距离
                pq.push(make_pair(d[e.to], e.to)); // 将e.to加入堆中
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s; // 输入点数、边数、源点
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w; // 输入一条边，起点为u，终点为v，边权为w
        G[u].push_back(Edge{v, w}); // 将边加入邻接表
    }

    fill(d, d + n, INF); // 初始化距离为无穷大
    dijkstra(s); // 求最短路径

    // 输出源点到各个点的最短距离
    for (int i = 0; i < n; i++) {
        cout << d[i] << " ";
    }
    cout << endl;

    return 0;
}

这样，我们就可以在邻接表储存结构下实现Dijkstra算法了。