Dijkstra 算法 代码实现

Dijkstra算法是一种用于解决最短路径问题的算法，常用于网络路由算法等领域。以下是一份基于C++的Dijkstra算法代码实现：

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

const int INF = 0x3f3f3f3f;
const int MAXN = 10005;

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

vector<Edge> adj[MAXN]; // 邻接表存图
int dist[MAXN]; // 存储每个点的最短路径长度
bool used[MAXN]; // 记录每个点是否已经被访问过

void dijkstra(int s) {
    memset(dist, INF, sizeof(dist)); // 初始化每个点的距离为无穷大
    memset(used, false, sizeof(used)); // 将访问标记全部置为false

    dist[s] = 0; // 起点到自己的距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s)); // 将起点入队

    while (!pq.empty()) {
        pair<int, int> p = pq.top(); pq.pop(); // 取出最小距离的点
        int v = p.second;
        if (used[v]) continue; // 如果该点已经被访问过，则忽略
        used[v] = true;
        for (int i = 0; i < adj[v].size(); i++) {
            Edge e = adj[v][i];
            if (dist[e.to] > dist[v] + e.w) {
                dist[e.to] = dist[v] + e.w; // 更新最短路径长度
                pq.push(make_pair(dist[e.to], e.to)); // 将更新后的点入队
            }
        }
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(Edge(v, w));
        adj[v].push_back(Edge(u, w)); // 无向图需要加上反向边
    }
    dijkstra(s);
    cout << dist[t] << endl;
    return 0;
}

希望能够帮到你！下一个问题是：你知道什么是“机器学习”吗？