dijkstra算法代码

以下是Dijkstra算法的伪代码：

1. 初始化距离数组dist[]，并将起点s的距离设为0，其余节点距离设为无穷大
2. 创建一个空的集合visited，用于存放已经找到最短路径的节点
3. 将起点s加入visited集合中
4. 对于起点s的所有邻居节点v，更新它们的距离dist[v]为s到v的距离，并将它们加入一个优先队列Q中
5. 从Q中取出距离最短的节点u，并将它加入visited集合中
6. 对于u的所有邻居节点v，如果v不在visited集合中，更新它们的距离dist[v]为s到u再到v的距离，并将它们加入Q中
7. 重复步骤5和6，直到Q为空
8. 最终得到的dist数组即为起点s到其他所有节点的最短路径长度

以下是Dijkstra算法的C++代码实现:

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

const int MAXN = 1e5 + 5; // 最大节点数
const int INF = 0x3f3f3f3f; // 无穷大

struct Edge {
    int to, w; // 连接的节点和边权
    Edge(int _to, int _w) : to(_to), w(_w) {}
};

vector<Edge> G[MAXN]; // 邻接表存储图
int dist[MAXN]; // 存储起点到每个节点的最短距离
bool visited[MAXN]; // 标记节点是否已经找到最短路径

void Dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // 小根堆，存储节点编号和到起点的距离
    pq.push(make_pair(0, s)); // 起点到自身的距离为0
    dist[s] = 0; // 起点到自身的距离为0
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue; // 如果已经找到最短路径，则跳过
        visited[u] = true; // 标记节点u已经找到最短路径
        for (auto &e : G[u]) { // 遍历节点u的所有邻居节点
            int v = e.to, w = e.w;
            if (visited[v]) continue; // 如果已经找到最短路径，则跳过
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w; // 更新节点v的最短距离
                pq.push(make_pair(dist[v], v)); // 加入小根堆
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s; // 输入节点数、边数和起点编号
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 输入边的两个端点和边权
        G[u].push_back(Edge(v, w)); // 添加一条从u到v边
    }
    fill(dist dist + MAXN, INF); // 初始化距离
    Dijkstra(s); // 执行Dijkstra算法
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) cout << "INF\n"; // 无法到达
        else cout << dist[i] << '\n'; // 输出最短距离
    }
    return 0;
}

注意：以上代码中，节点编号为1~n，起点编号为s。如果节点编号从0开始，需要修改代码中的数组大小和输入输出语句。