ホーム > libalgo

無向グラフの二点間最短路

概要

無向グラフの $s$-$t$ 最短路を,両側からダイクストラすることで求める. $\mu = \min_{e = vw \in E}$ { s-v 最短距離 + $e$ の重み + w-t 最短距離} が,2 つのヒープの先頭の和以上になったら $\mu$ を返す.

使い方

グラフ,始点,終点を渡す.負辺と有向グラフはダメ.

計算量

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

実装

Weight bidirectional_dijkstra(const Graph &g, int s, int t) {
    if (s == t) return 0;
    constexpr Weight INF = std::numeric_limits<Weight>::max() / 2;
    int n = g.size();
    std::vector<Weight> dist[2];
    dist[0] = dist[1] = std::vector<Weight>(n, INF);
    dist[0][s] = dist[1][t] = 0;
    using state = std::pair<Weight, int>;
    std::priority_queue<state, std::vector<state>, std::greater<state>> pq[2];
    pq[0].emplace(0, s);
    pq[1].emplace(0, t);
    Weight mu = INF;
    while (pq[0].size() && pq[1].size()) {
        if (pq[0].top().first + pq[1].top().first >= mu) break;
        int k = pq[0].top().first <= pq[1].top().first ? 0 : 1;
        Weight d;
        int v;
        std::tie(d, v) = pq[k].top();
        pq[k].pop();
        if (d < dist[k][v]) continue;
        for (auto &e : g[v]) {
            Weight w = e.dst;
            if (dist[k][w] > dist[k][v] + e.weight) {
                dist[k][w] = dist[k][v] + e.weight;
                pq[k].emplace(dist[k][w], w);
                mu = std::min(mu, dist[k][v] + e.weight + dist[1 - k][w]);
            }
        }
    }
    return mu;
}

検証

ARC012D http://abc012.contest.atcoder.jp/submissions/1098600

参考文献

http://tatanaideyo.hatenablog.com/entry/2015/11/01/031713