基于Dijsktra算法的最短路径求解用c++编写

以下是基于Dijsktra算法的最短路径求解的C++代码示例：

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

using namespace std;

const int MAXN = 1005;  // 最大节点数
struct Edge {
    int to, w;
    Edge(int _to, int _w) : to(_to), w(_w) {}
};
vector<Edge> G[MAXN];  // 邻接表存图
int d[MAXN];  // 存储最短路径长度
bool vis[MAXN];  // 标记节点是否已访问

void dijkstra(int s) {
    fill(d, d + MAXN, INT_MAX);  // 初始化距离为无穷大
    fill(vis, vis + MAXN, false);  // 初始化所有节点为未访问状态
    d[s] = 0;  // 起点距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;  // 小根堆
    q.push(make_pair(0, s));  // 将起点加入堆
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &e: G[u]) {
            int v = e.to;
            if (d[v] > d[u] + e.w) {
                d[v] = d[u] + e.w;
                if (!vis[v]) q.push(make_pair(d[v], v));
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;  // n为节点数，m为边数，s为起点编号
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));  // 存储有向图
    }
    dijkstra(s);
    for (int i = 1; i <= n; ++i) {
        if (d[i] == INT_MAX) cout << "INF" << endl;  // 输出无穷大
        else cout << d[i] << endl;
    }
    return 0;
}

在这个示例中，我们使用了邻接表存储图，并使用了小根堆来优化Dijsktra算法的时间复杂度。在主函数中，我们首先输入节点数、边数和起点编号，然后读入边的信息，存储为邻接表。最后调用`dijkstra()`函数求解最短路径，并输出结果。