Day 063-Q1 — Fibonacci Heap応用（Dijkstra高速化・decrease-key O(1) amortized）

2026-06-16 赤色 Master / Phase 8+ ★★★★★★★★★ Fibonacci Heap / Amortized / 優先度付きキュー

問題

$N$ 頂点 $M$ 辺の重み付き有向グラフが与えられる。頂点 $1$ からすべての頂点への最短距離を求めよ。ただし以下の 追加クエリ が $Q$ 個オンラインで与えられる：

  • decrease u w: 頂点 $u$ への暫定距離を $w$ に強制更新する（必ず現在値より小さい値が来る）。クエリ直後の全頂点への最短距離を再計算して答えよ。

制約

パラメータ範囲
$N$$2 \le N \le 10^5$
$M$$1 \le M \le 3 \times 10^5$
$Q$$0 \le Q \le 10^4$
$w_i$$1 \le w_i \le 10^9$
グラフ非負重み

入出力例

入力例 1

4 5 2
1 2 3
1 3 6
2 3 1
2 4 5
3 4 2
decrease 4 7
decrease 3 2

出力例 1

Initial: 0 3 4 6
After decrease 4 7: 0 3 4 6
After decrease 3 2: 0 3 2 4

decrease クエリで dist[3]=2 になると、3→4 の辺（コスト2）より dist[4]=4 に更新される。

概念図: Fibonacci Heap vs Binary Heap

計算量比較 操作 Binary Heap Fib Heap insert O(log N) O(1) find-min O(1) O(1) delete-min O(log N) O(log N)* decrease-key O(log N) O(1)* union O(N) O(1) Dijkstra総計 O((N+M)logN) O(M+NlogN) * amortized Lazy Deletion で decrease-key をシミュレート decrease-key(u, w): 1. dist[u] = w を更新 2. heap に (w, u) を push （古い (old_d, u) は heap に残る） pop 時: if d > dist[u]: skip（古いエントリ） else: 処理（最新エントリ） 時間計算量: O(M log M) （エントリ数が M 個以下 → log M）

ヒント（段階的開示）

ヒント1: 方向性
Fibonacci Heap の decrease-key は $O(1)$ amortized。Python では直接実装が煩雑なため、lazy deletion による heapq シミュレーションを使う。decrease クエリ後は dist[u] を更新し新しいエントリを push、pop 時に古いエントリをスキップする。
ヒント2: アプローチ
  • decrease クエリ: dist[u] = w; heappush(heap, (w, u))
  • pop 時: if d > dist[u]: continue（lazy deletion）
  • decrease 後に relax() を呼ぶと、更新された dist から再 propagation される
ヒント3: コード骨格 
def relax():
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue  # lazy deletion
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

# decrease クエリ処理
dist[u] = w
heapq.heappush(heap, (w, u))
relax()

模範解答 (Python)

import heapq
import sys
input = sys.stdin.readline

def solve():
    N, M, Q = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))

    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0
    heap = [(0, 1)]

    def relax():
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            for v, w in graph[u]:
                nd = dist[u] + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(heap, (nd, v))

    relax()
    res = [dist[i] if dist[i] < INF else -1 for i in range(1, N + 1)]
    print("Initial:", *res)

    for _ in range(Q):
        line = input().split()
        u, w = int(line[1]), int(line[2])
        if w < dist[u]:
            dist[u] = w
            heapq.heappush(heap, (w, u))
        relax()
        res = [dist[i] if dist[i] < INF else -1 for i in range(1, N + 1)]
        print(f"After decrease {u} {w}:", *res)

solve()

Step-by-Step 解説

Step 1: Fibonacci Heap の概念

Fibonacci Heap は amortized 計算量が優れた優先度付きキュー。decrease-key が $O(1)$ amortized のため、Dijkstra 全体が $O(M + N\log N)$ になる。Python では直接実装が煩雑なため、lazy deletion による heapq シミュレーションを使う。

Step 2: Lazy Deletion の仕組み

  • ヒープに古いエントリが残っていても dist[u] と比較して無視する
  • decrease クエリ後は dist[u] を更新し、新しいエントリを push する
  • pop 時に d > dist[u] なら skip（これが lazy deletion）

Step 3: オンライン decrease クエリ

decrease クエリは「外部からの距離強制更新」。更新後、その頂点を始点として Dijkstra の relaxation を再開する。visited フラグは使わず dist 値のみで判断する。

Step 4: 計算量分析

処理計算量
初期 Dijkstra$O(M \log N)$
各 decrease クエリ最悪 $O(M \log N)$
合計$O((Q+1) \cdot M \log N)$

よくあるミス

ミス原因正しい書き方
decrease後にvisitedをリセットしない 確定済み扱いで再探索されない dist値のみで判断し visitedは使わない
d > dist[u] チェック忘れ 古いエントリを処理してしまう pop直後に必ずチェック
decrease値が現在値より大きい 最短距離が増加する矛盾 if w < dist[u] の条件確認

次のステップ

発展問題: Radix Heap を実装して整数重み Dijkstra を $O(M + N\sqrt{W})$ に高速化せよ（$W$ は最大辺重み）。

自己評価