Day 082-Q1 | Fibonacci Heap 応用（Dijkstra 高速化）

問題

$N$ 頂点 $M$ 辺の重み付き有向グラフが与えられる。頂点 $1$ を始点として全頂点への最短距離を求めよ。

$N \le 10^6$, $M \le 5 \times 10^6$ の大規模グラフで、通常の二分ヒープ Dijkstra では TLE。Fibonacci Heap を用いて decrease-key を $O(1)$ amortized で行い、全体 $O(M + N \log N)$ で解け。

制約

パラメータ	範囲	備考
$N$	$\le 10^6$	頂点数
$M$	$\le 5 \times 10^6$	辺数
$w_i$	$1 \le w_i \le 10^9$	辺重み（非負）

入出力例

入力例1

出力例1

0 7 3 9 14

概念図: Fibonacci Heap の構造と操作

ヒント

ヒント1（方向性）

Fibonacci Heap は insert, find-min, extract-min, decrease-key, merge をサポート。decrease-key が $O(1)$ amortized である点が最大の特徴。Dijkstra に組み込むと全体 $O(M + N \log N)$ になる。

ヒント2（アプローチ）

Fibonacci Heap の核心は「遅延マージ」と「カスケードカット」。extract-min 時に consolidate（度数ごとにまとめる）を行うが、decrease-key では親との切り離しのみ行う。カスケードカットによって各ノードの損失は限定される。

ヒント3（ほぼ答え）

class FibNode:
    def __init__(self, key, val):
        self.key = key; self.val = val
        self.degree = 0; self.marked = False
        self.parent = self.child = None
        self.left = self.right = self

def decrease_key(self, node, new_key):
    node.key = new_key
    if node.parent and node.key < node.parent.key:
        self._cut(node, node.parent)
        self._cascade_cut(node.parent)
    if node.key < self.min_node.key:
        self.min_node = node

模範解答

import sys
from math import log2
input = sys.stdin.readline

def solve():
    N, M = 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

    class Node:
        __slots__ = ['key','val','degree','marked','parent','child','left','right']
        def __init__(self, key, val):
            self.key = key; self.val = val
            self.degree = 0; self.marked = False
            self.parent = self.child = None
            self.left = self.right = self

    class FibHeap:
        def __init__(self):
            self.min_node = None; self.n = 0

        def _add_to_root(self, node):
            node.parent = None
            if self.min_node is None:
                node.left = node.right = node
                self.min_node = node
            else:
                node.right = self.min_node.right
                node.left = self.min_node
                self.min_node.right.left = node
                self.min_node.right = node
                if node.key < self.min_node.key:
                    self.min_node = node

        def insert(self, key, val):
            nd = Node(key, val)
            self._add_to_root(nd)
            self.n += 1
            return nd

        def extract_min(self):
            z = self.min_node
            if z is None: return None
            if z.child:
                children = []
                c = z.child; start = c
                while True:
                    children.append(c); c = c.right
                    if c is start: break
                for c in children: self._add_to_root(c)
            z.left.right = z.right; z.right.left = z.left
            self.n -= 1
            if z == z.right:
                self.min_node = None
            else:
                self.min_node = z.right
                self._consolidate()
            return z

        def _consolidate(self):
            max_deg = int(log2(self.n + 1)) + 2 if self.n > 0 else 2
            A = [None] * (max_deg + 1)
            roots = []
            cur = self.min_node
            while True:
                roots.append(cur); cur = cur.right
                if cur is self.min_node: break
            for w in roots:
                x = w; d = x.degree
                while d < len(A) and A[d] is not None:
                    y = A[d]
                    if x.key > y.key: x, y = y, x
                    self._link(y, x)
                    A[d] = None; d += 1
                if d >= len(A): A.extend([None]*(d-len(A)+1))
                A[d] = x
            self.min_node = None
            for node in A:
                if node is None: continue
                node.left = node.right = node
                if self.min_node is None:
                    self.min_node = node
                else:
                    node.right = self.min_node.right
                    node.left = self.min_node
                    self.min_node.right.left = node
                    self.min_node.right = node
                    if node.key < self.min_node.key:
                        self.min_node = node

        def _link(self, y, x):
            y.left.right = y.right; y.right.left = y.left
            y.parent = x
            if x.child is None:
                x.child = y; y.left = y.right = y
            else:
                y.right = x.child.right; y.left = x.child
                x.child.right.left = y; x.child.right = y
            x.degree += 1; y.marked = False

        def decrease_key(self, node, k):
            node.key = k
            p = node.parent
            if p and node.key < p.key:
                self._cut(node, p)
                self._cascade_cut(p)
            if node.key < self.min_node.key:
                self.min_node = node

        def _cut(self, x, y):
            if x.right == x:
                y.child = None
            else:
                x.left.right = x.right; x.right.left = x.left
                if y.child == x: y.child = x.right
            y.degree -= 1
            self._add_to_root(x); x.marked = False

        def _cascade_cut(self, y):
            z = y.parent
            if z:
                if not y.marked: y.marked = True
                else: self._cut(y, z); self._cascade_cut(z)

    fh = FibHeap()
    handles = [None] * (N+1)
    handles[1] = fh.insert(0, 1)
    for i in range(2, N+1):
        handles[i] = fh.insert(INF, i)

    while fh.min_node:
        nd = fh.extract_min()
        u = nd.val; d = nd.key
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                fh.decrease_key(handles[v], dist[v])

    print(*dist[1:])

solve()

Step-by-Step 解説

Step 1: Fibonacci Heap の優位性

操作	Binary Heap	Fibonacci Heap
insert	$O(\log N)$	$O(1)$
extract-min	$O(\log N)$	$O(\log N)$ amortized
decrease-key	$O(\log N)$	$O(1)$ amortized
merge	$O(N)$	$O(1)$

Dijkstra では decrease-key が $O(M)$ 回、extract-min が $O(N)$ 回 → 全体 $O(M + N \log N)$。

Step 2: decrease-key とカスケードカット

1. キーを更新 → 2. 親より小さければ親から切り離し根リストへ（cut）→ 3. cut された親が marked なら再帰的に cut（cascade cut）

各ノードの切り離し回数を 1 回に制限することで amortized $O(1)$ を保証。

Step 3: consolidate（統合）

extract-min 後、根リスト内の同次数木をマージして各次数に最高1本になるよう整理。最大次数 $O(\log N)$ なので $O(\log N)$ amortized。

Step 4: handles 配列の重要性

handles = [None] * (N+1)
handles[1] = fh.insert(0, 1)
# ...
fh.decrease_key(handles[v], dist[v])  # ノードポインタで直接アクセス

よくあるミス

ミス	原因	正しい書き方
双方向リストの更新漏れ	left/right 両側を更新する必要	`x.left.right = x.right; x.right.left = x.left`
consolidate 後の min_node 更新漏れ	全根を再スキャン	A リスト構築後に全非 None を再リンク
handles 配列なしで decrease-key	どのノードか不明	頂点ごとにノードポインタを保持
N=0 での log2(0) エラー	FibHeap 空時	`if self.n > 0` でガード

次のステップ

発展問題: Prim の最小全域木を Fibonacci Heap で $O(M + N \log N)$ に高速化
参考: Fredman & Tarjan (1987) "Fibonacci heaps and their uses in improved network optimization algorithms"

自己評価

理解度: 完全理解 / おおむね理解 / 要復習

自分の回答:

気づき・メモ: