dijkstra最短路径算法

Dijkstra算法是一种经典的单源最短路径算法，用于在加权图中寻找从源到所有其他节点的最短路径。Dijkstra算法的基本思想是通过不断更新起点到各个顶点之间的最短路径来求解最短路径问题。具体实现时，我们可以使用一个优先队列来维护当前未确定最短路径的顶点，每次取出距离最小的顶点进行松弛操作，直到所有顶点的最短路径被确定。

下面是Dijkstra算法的伪代码：

1. 初始化起点到各个顶点的最短路径长度为正无穷，起点的最短路径长度为0。
2. 将起点加入优先队列。
3. 当优先队列非空时，取出距离起点最近的顶点u，并标记已被确定最短路径。
4. 对于每个与u相邻的顶点v，如果起点到v的最短路径可以通过u进行松弛（即起点到u的路径长度加上u到v的边权小于起点到v的最短路径长度），则更新起点到v的最短路径长度，并将v加入优先队列。
5. 重复步骤3-4，直到所有顶点的最短路径被确定。

下面是使用C++实现Dijkstra算法的示例代码：

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

using namespace std;

const int INF = 0x3f3f3f3f;

vector<vector<pair<int, int>>> edge; // 存储图的邻接表
vector<int> dist; // 存储起点到各个顶点的最短路径长度
vector<bool> vis; // 存储每个顶点的最短路径是否已经确定

void dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 优先队列按照距离从小到大排序
    dist[s] = 0;
    q.push({0, s});

    while(!q.empty()) {
        int u = q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;

        // 对于每个与u相邻的顶点v，如果起点到v的最短路径可以通过u进行松弛，则更新起点到v的最短路径长度，并将v加入优先队列
        for(auto j : edge[u]) {
            int v = j.first, w = j.second;
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
}

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

    // 初始化
    edge.resize(n+1);
    dist.resize(n+1, INF);
    vis.resize(n+1, false);

    // 构建邻接表
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w}); // 如果是无向图，需要将边加入反向边
    }

    // 运行Dijkstra算法
    int s;
    cin >> s;
    dijkstra(s);

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

    return 0;
}

在上述示例代码中，我们使用了一个优先队列来维护当前未确定最短路径的顶点，每次取出距离最小的顶点进行松弛操作，直到所有顶点的最短路径被确定。需要注意的是，在实现过程中我们使用了vector来存储邻接表、距离和是否已经确定最短路径等信息，并在初始化时将起点到各个顶点的最短路径长度设为正无穷，起点的最短路径长度设为0。