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

Dijkstra算法是一种求解单源最短路径的贪心算法，适用于有权图，可以使用邻接表作为存储结构进行实现。下面是具体实现步骤：

1. 初始化：将源点到各个顶点的最短路径length初始化为无穷大，源点到自身的最短路径为0。

2. 将源点加入到已访问的集合中。

3. 对于源点所有直接相邻的顶点，更新它们到源点的最短距离length，并记录下权值最小的边。

4. 从未访问的顶点中选取与源点距离最近的顶点，将其加入到已访问的集合中，并重复步骤3，直到所有顶点都被访问为止。

下面是基于邻接表存储结构的Dijkstra算法的C++实现代码：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
    int to, weight;
    Edge(int t, int w) :to(t), weight(w) {}
};

typedef vector<vector<Edge>> Graph;

void dijkstra(const Graph& g, int s, vector<int>& dist, vector<int>& prev) {
    int n = g.size();
    dist.assign(n, INT_MAX);
    dist[s] = 0;
    prev.assign(n, -1);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto e : g[u]) {
            int v = e.to, w = e.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
    }

    vector<int> dist, prev;
    dijkstra(g, s, dist, prev);

    for (int i = 0; i < n; i++) {
        cout << "distance from " << s << " to " << i << " is " << dist[i] << endl;
    }

    return 0;
}

其中，Graph是邻接表存储结构的图，使用vector<vector<Edge>>表示。在dijkstra函数中，使用priority_queue来维护未访问的顶点集合，按照到源点距离的从小到大的顺序选择下一个访问的顶点。在更新某个顶点的最短路径时，同时记录下使其路径长度最小的边的信息，以便在后续遍历中可以重构最短路径。