経路復元付きDijkstra法
(graph/dijkstra_restore.cpp)

• View this file on GitHub
• Last update: 2026-03-12 14:17:55+09:00

説明

単一始点最短路と最短路木の親を求める。 辺重みが非負のときに使う。 計算量は $O((V + E) log V)$。

できること

• DijkstraRestoreResult<T> dijkstra_restore(int s, const vector<vector<edge<T>>>& g) 始点 s からの最短距離と親配列を返す。未到達頂点の距離は INF<T>、親は -1
• vector<int> restore_path(int s, int t, const vector<int>& parent) 親配列から s -> t の頂点列を復元して返す。復元できなければ空配列

使い方

edge<T> の隣接リストを作って dijkstra_restore を呼ぶ。 頂点列が必要なら返ってきた parent を restore_path に渡す。

vector<vector<edge<long long>>> g(n);
g[u].emplace_back(v, w);
auto res = dijkstra_restore(0, g);
auto path = restore_path(0, t, res.parent);

実装上の補足

同じ距離の候補が複数あるとき、親は更新しない。 返る経路は最短路のひとつであり、一意性は保証しない。

Depends on

• graph/dijkstra_common.cpp

Verified with

• test/yosupo_shortest_path.test.cpp

Code

#include "dijkstra_common.cpp"

template <typename T>
struct DijkstraRestoreResult {
    vector<T> dist;
    vector<int> parent;
};

template <typename T>
DijkstraRestoreResult<T> dijkstra_restore(int s, const vector<vector<edge<T>>> &G) {
    vector<int> parent((int)G.size(), -1);
    DijkstraPriorityQueue<T> Q;
    auto dist = dijkstra_internal(s, G, Q, [&](int v, const edge<T> &e) {
        parent[e.to] = v;
    });
    return {dist, parent};
}

vector<int> restore_path(int s, int t, const vector<int> &parent) {
    vector<int> path;
    if (t < 0 || t >= (int)parent.size()) return path;
    int v = t;
    while (v != -1) {
        path.push_back(v);
        if (v == s) {
            reverse(path.begin(), path.end());
            return path;
        }
        v = parent[v];
    }
    path.clear();
    return path;
}

/**
 * @brief 経路復元付きDijkstra法
 */

#line 1 "graph/dijkstra_common.cpp"



template <typename T>
struct edge {
    int from, to;
    T cost;

    edge(int to, T cost) : from(-1), to(to), cost(cost) {}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};

template <typename T>
struct DijkstraPriorityQueue {
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> q;

    bool empty() const { return q.empty(); }

    void push(T cost, int v) {
        q.emplace(cost, v);
    }

    pair<T, int> pop() {
        auto res = q.top();
        q.pop();
        return res;
    }
};

template <typename T, class Queue, class OnRelax>
vector<T> dijkstra_internal(int s, const vector<vector<edge<T>>> &G, Queue &Q, OnRelax on_relax) {
    int n = (int)G.size();
    vector<T> dist(n, INF<T>);
    dist[s] = 0;
    Q.push(T(0), s);
    while (!Q.empty()) {
        auto [cost, v] = Q.pop();
        if (dist[v] < cost) continue;
        for (auto &&e : G[v]) {
            T nxt = cost + e.cost;
            if (dist[e.to] <= nxt) continue;
            dist[e.to] = nxt;
            on_relax(v, e);
            Q.push(nxt, e.to);
        }
    }
    return dist;
}

template <typename T, class Queue>
vector<T> dijkstra_internal(int s, const vector<vector<edge<T>>> &G, Queue &Q) {
    return dijkstra_internal(s, G, Q, [](int, const edge<T> &) {});
}


#line 2 "graph/dijkstra_restore.cpp"

template <typename T>
struct DijkstraRestoreResult {
    vector<T> dist;
    vector<int> parent;
};

template <typename T>
DijkstraRestoreResult<T> dijkstra_restore(int s, const vector<vector<edge<T>>> &G) {
    vector<int> parent((int)G.size(), -1);
    DijkstraPriorityQueue<T> Q;
    auto dist = dijkstra_internal(s, G, Q, [&](int v, const edge<T> &e) {
        parent[e.to] = v;
    });
    return {dist, parent};
}

vector<int> restore_path(int s, int t, const vector<int> &parent) {
    vector<int> path;
    if (t < 0 || t >= (int)parent.size()) return path;
    int v = t;
    while (v != -1) {
        path.push_back(v);
        if (v == s) {
            reverse(path.begin(), path.end());
            return path;
        }
        v = parent[v];
    }
    path.clear();
    return path;
}

/**
 * @brief 経路復元付きDijkstra法
 */

Back to top page