最短路径c++

以下是使用 Dijkstra 算法求解最短路径的 C++ 代码示例：

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

using namespace std;

#define MAX_N 1000 // 最大顶点数

struct Edge {
    int to;     // 边的目标顶点
    int cost;   // 边权重
};

vector<Edge> g[MAX_N]; // 图的邻接表表示
int d[MAX_N];           // 存储起点到各顶点的最短距离
bool used[MAX_N];       // 最短距离是否已经确定

void dijkstra(int s) {
    // 初始化
    fill(d, d + MAX_N, INT_MAX);
    fill(used, used + MAX_N, false);
    d[s] = 0;

    // 创建小根堆，存储未确定最短距离的顶点
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;

    // 把起点加入小根堆
    q.push(make_pair(0, s));

    // 计算最短距离
    while (!q.empty()) {
        // 取出小根堆中最小距离的顶点
        pair<int, int> p = q.top();
        q.pop();
        int v = p.second;

        // 如果最短距离已经确定，就跳过
        if (used[v]) continue;

        // 标记最短距离已经确定
        used[v] = true;

        // 更新相邻顶点的最短距离
        for (int i = 0; i < g[v].size(); i++) {
            Edge e = g[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int main() {
    // 读入顶点数、边数和起点编号
    int n, m, s;
    cin >> n >> m >> s;

    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back(Edge{v, c});
    }

    // 计算最短距离
    dijkstra(s);

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

    return 0;
}

其中，`g` 表示图的邻接表，`d` 表示起点到各顶点的最短距离，`used` 表示最短距离是否已经确定。函数 `dijkstra` 是求解最短路径的核心函数，它使用小根堆来存储未确定最短距离的顶点，并逐步计算出最短距离。在主函数中，先读入顶点数、边数和起点编号，然后读入边，最后调用 `dijkstra` 函数计算最短距离并输出结果。