利用邻接表生成dijkstra算法

Dijkstra算法是一种用于求解图中最短路径的贪心算法。它的基本思想是从起点开始，每次选择当前最短的路径并更新与其相邻的节点的距离，直到到达终点或者所有节点都被遍历。

邻接表是一种表示图的数据结构，它将每个节点的相邻节点存储在一个链表中。使用邻接表可以有效地表示稀疏图，降低空间复杂度。

下面是利用邻接表生成Dijkstra算法的伪代码：

1. 初始化起点到所有节点的距离为无穷大，起点到自己的距离为0。
2. 将起点加入待处理节点集合。
3. while 待处理节点集合不为空：
1. 从待处理节点集合中选择距离最短的节点。
2. 将该节点从待处理节点集合中删除。
3. 遍历该节点的所有相邻节点：
1. 如果该相邻节点未被处理过，则将其加入待处理节点集合。
2. 计算起点到该相邻节点的距离，并更新该相邻节点的最短距离。
4. 返回起点到终点的最短距离。

实现上述算法的关键在于如何存储图的信息。可以使用一个数组dist记录起点到各个节点的最短距离，使用一个数组visited记录每个节点是否已经被处理过，使用一个优先队列（如堆）来存储待处理的节点。邻接表可以用链表来存储。

下面是C++的实现代码：

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

using namespace std;

typedef pair<int, int> P; // P.first表示距离，P.second表示节点编号

const int MAXN = 1005;
const int INF = INT_MAX;

vector<P> adj[MAXN]; // 邻接表
int dist[MAXN]; // 起点到各个节点的最短距离
bool visited[MAXN]; // 记录节点是否已经被处理过

void dijkstra(int s) {
    // 初始化
    fill(dist, dist + MAXN, INF);
    dist[s] = 0;
    visited[s] = true;
    priority_queue<P, vector<P>, greater<P>> pq;
    for (auto& p : adj[s]) {
        dist[p.second] = p.first;
        pq.push(p);
    }

    // 循环处理节点
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int u = p.second;
        if (visited[u]) continue; // 节点已经被处理过，跳过
        visited[u] = true;
        for (auto& v : adj[u]) {
            if (visited[v.second]) continue; // 相邻节点已经被处理过，跳过
            int newDist = dist[u] + v.first;
            if (newDist < dist[v.second]) { // 更新相邻节点的最短距离
                dist[v.second] = newDist;
                pq.push(make_pair(newDist, v.second));
            }
        }
    }
}

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;
        adj[u].push_back(make_pair(w, v));
    }

    // 运行Dijkstra算法
    dijkstra(s);

    // 输出结果
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
    return 0;
}