实现Dijkstra最短路径算法

Dijkstra算法是一种经典的单源最短路径算法。它的基本思路是从源点开始，每次选择当前离源点最近的一个顶点，并且用该顶点更新其它顶点的距离值。具体实现步骤如下：

1. 创建一个数组dist，表示源点到各个顶点的距离，初始化为无穷大。
2. 将源点的dist值设置为0。
3. 创建一个数组visited，表示顶点是否已经被访问过，初始化为false。
4. 重复以下步骤，直到所有顶点都被访问过：
- 选取dist值最小的未访问过的顶点u。
- 将u标记为已访问。
- 对于u的每个邻接顶点v，如果v未被访问过，且从源点到v的距离比当前dist[v]更小，则更新dist[v]的值为从源点到u再到v的距离。
5. 返回dist数组，其中dist[i]表示从源点到顶点i的最短路径长度。

下面是Dijkstra算法的C++实现代码：

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

const int INF = 1e9;

vector<pair<int, int>> adj[100001];
int dist[100001];

void dijkstra(int src) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});
    dist[src] = 0;
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (dist[u] < pq.top().first) continue;
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m, src;
    cin >> n >> m >> src;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    fill(dist, dist + n + 1, INF);
    dijkstra(src);
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
    return 0;
}

其中，adj数组用来存储图的邻接表表示，dist数组用来存储源点到各个顶点的距离，priority_queue用来实现选择dist值最小的未访问过的顶点。在实现中，我们使用了C++11中的range-based for循环和结构化绑定，使代码更加简洁易读。