最短路木

概要

頂点 $r$ からダイクストラ探索を行い，通った方向の辺のみからなる根付き木を返す．木を根付き木にしたいときなどにも使う (log が付くがほとんど問題ない)．

計算量

$O((E+V) \log V)$

実装

Graph shortest_path_tree(const Graph &g, int root = 0) {
    int n = g.size();
    constexpr Weight INF = std::numeric_limits<Weight>::max() / 2;
    std::vector<const Edge *> to(n, nullptr);
    std::vector<int> dist(n, INF);
    std::priority_queue<std::tuple<int, int>> pq;
    dist[root] = 0;
    pq.emplace(0, root);
    while (pq.size()) {
        Weight d;
        int v;
        std::tie(d, v) = pq.top();
        pq.pop();
        d = -d;
        if (dist[v] < d) continue;
        for (auto &e : g[v]) {
            if (dist[e.dst] > dist[v] + e.weight) {
                dist[e.dst] = dist[v] + e.weight;
                pq.emplace(-dist[e.dst], e.dst);
                to[e.dst] = &e;
            }
        }
    }
    Graph res(n);
    for (auto e : to)
        if (e) res[e->src].emplace_back(*e);
    return res;
}