Day 144-Q4 | 双方向ダイクストラ法

問題

$N$ 頂点 $M$ 辺の無向重み付きグラフが与えられる。頂点 $s$ から頂点 $t$ への最短距離を、双方向ダイクストラ法で求めよ。

アルゴリズムの骨子

$s$発の前向き探索($d_F$)と$t$発の逆向き探索($d_B$)を独立したキューで同時に走らせる
各ステップでキュー先頭が小さい方を1手だけ進める
頂点$v$が両方で確定したら暫定解を$\min(\text{暫定解}, d_F(v)+d_B(v))$で更新
前向き先頭+後ろ向き先頭が暫定解以上になったら打ち切り

入力形式

N M
u_1 v_1 w_1
:
u_M v_M w_M
s t

制約

$2 \le N \le 2\times10^5$

$1 \le M \le 2\times10^5$

$1 \le w_i \le 10^9$

非連結なら-1

入出力例

入力例1

出力例1

最短経路 1→2→3→5→6（3+2+7+4=16）。前向き探索と後ろ向き探索が中間付近で出会い早期終了する。

概念図：2つの半径 r/2 の球

ヒント（段階的開示）

ヒント1（方向性）

片方向のダイクストラ法は目的地から遠くまで一様に広がる。$s$側と$t$側の両方から同時に球を広げれば、2つの球が触れ合った時点で答えが分かるはずだが「触れ合った」の厳密な定義と停止タイミングが技術的に難しい。

ヒント2（アプローチ）

正しい停止条件は「前向きキュー先頭値+後ろ向きキュー先頭値 ≥ 暫定解」。まだ未確定の頂点は前向きなら距離≥前向き先頭値、後ろ向きなら≥後ろ向き先頭値であることから、この条件が満たされればそれ以上探索しても暫定解を更新できないことが三角不等式的に保証される。

ヒント3（誘導）

while pqF and pqB:
    if pqF[0][0] + pqB[0][0] >= best:
        break  # 停止条件
    if pqF[0][0] <= pqB[0][0]:
        d, u = heapq.heappop(pqF)
        if doneF[u]: continue
        doneF[u] = True
        if doneB[u]:
            best = min(best, distF[u] + distB[u])
        # 隣接辺を緩和...
    else:
        # 後ろ向きも同様

模範解答 (Python)

import sys
import heapq

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))
    s = int(data[idx]); idx += 1
    t = int(data[idx]); idx += 1

    INF = float('inf')
    if s == t:
        print(0)
        return

    distF = [INF] * (N + 1)
    distB = [INF] * (N + 1)
    doneF = [False] * (N + 1)
    doneB = [False] * (N + 1)
    distF[s] = 0
    distB[t] = 0
    pqF = [(0, s)]
    pqB = [(0, t)]
    best = INF

    while pqF and pqB:
        if pqF[0][0] + pqB[0][0] >= best:
            break

        if pqF[0][0] <= pqB[0][0]:
            d, u = heapq.heappop(pqF)
            if doneF[u]:
                continue
            doneF[u] = True
            if doneB[u]:
                best = min(best, distF[u] + distB[u])
            for v, w in adj[u]:
                nd = d + w
                if nd < distF[v]:
                    distF[v] = nd
                    heapq.heappush(pqF, (nd, v))
                    if doneB[v]:
                        best = min(best, nd + distB[v])
        else:
            d, u = heapq.heappop(pqB)
            if doneB[u]:
                continue
            doneB[u] = True
            if doneF[u]:
                best = min(best, distB[u] + distF[u])
            for v, w in adj[u]:
                nd = d + w
                if nd < distB[v]:
                    distB[v] = nd
                    heapq.heappush(pqB, (nd, v))
                    if doneF[v]:
                        best = min(best, nd + distF[v])

    print(best if best < INF else -1)

main()

Step-by-Step 解説

1なぜ「両方確定=答え」では不十分か
頂点vが両方で確定した瞬間の$d_F(v)+d_B(v)$は経路長の候補にすぎず、まだ未確定の別頂点を経由する方が短い可能性が残る。

2停止条件の導出
前向き先頭値α、後ろ向き先頭値βとすると未確定頂点経由の経路長は必ず≥α+β。よってα+β≥bestで打ち切れる。

3小さい方のキューを優先する理由
片方だけ進めると探索範囲が偏り双方向探索の利点(半径r/2の球2つ)が失われる。

4無向/有向グラフの違い
有向グラフでは後ろ向き探索に辺の向きを逆にした逆グラフが必要。

5計算量
最悪計算量はO(M log N)で片方向と同じだが、実測の探索ノード数が大きく減ることが多い。

よくあるミス

ミス	原因	正しい書き方
停止条件を「片方がゴールに到達したら終了」としてしまう	素朴な「両方向がゴールに着いたら止める」という誤解	正しくは前向きキュー先頭+後ろ向きキュー先頭≥best
両方確定した頂点の経由コストをbestに反映し忘れる	確定処理のたびに逆方向の確定チェックを怠る	頂点確定のたびに逆方向で確定済みかを確認しbestを更新する
有向グラフなのに逆向きグラフを作らず同じ隣接リストを使い回す	無向グラフ用の実装をそのまま流用してしまう	有向グラフでは後ろ向き探索用に辺の向きを反転させたradjを別途構築する
優先度付きキューの先頭を覗く際にポップしてしまう	heappopとpq[0]（覗くだけ）を混同する	停止条件判定にはpq[0][0]を使い実際に進める側だけheappopする
古いエントリを考慮せずbestを誤って更新する	ヒープに複数回同じ頂点がプッシュされることを想定していない	ポップ時にdone配列で真に確定済みかを確認しスキップする

次のステップ

発展: Q2のALT法と組み合わせた「双方向A*」を実装し、単純な双方向ダイクストラ法との探索ノード数の差を比較せよ。
発展2: 複数クエリが飛んでくる場合、コントラクション階層(Contraction Hierarchies)など前処理型の手法と双方向探索の使い分けを整理せよ。

自己評価

完全理解おおむね理解要復習

Day 144-Q4 — 双方向ダイクストラ法（前向き/後ろ向き同時探索の停止条件）

問題