Day 082-Q2 — 代数的パス問題（行列半環・熱帯半環 Dijkstra）

問題

$N$ 頂点の重み付き有向グラフが与えられる。以下のクエリを処理せよ：

• min-sum: 頂点 $s$ から全頂点への最短距離（最小和パス）
• max-product: 辺の重みを「成功確率」として、$s$ から各頂点への最大積パス

これらを統一的な代数的パス問題（半環 $(K, \oplus, \otimes, \bar{0}, \bar{1})$）の枠組みで解け。

入出力例

4 5
1 2 3
1 3 8
2 3 2
2 4 5
3 4 1
3
1 min-sum
1 max-product
2 min-sum

0 3 5 6
1 0.333333 0.333333 0.333333
0 0 2 3

概念図: 半環の統一枠組み

ヒント

def dijkstra_maxprod(src, N, W):
    import heapq
    best = [0.0]*N; best[src] = 1.0
    hq = [(-1.0, src)]
    while hq:
        neg_d, u = heapq.heappop(hq)
        d = -neg_d
        if d < best[u]: continue
        for v in range(N):
            nb = best[u] * W[u][v]
            if nb > best[v]:
                best[v] = nb
                heapq.heappush(hq, (-nb, v))
    return best

模範解答

import sys
import heapq
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    INF = float('inf')
    W_ms = [[INF]*N for _ in range(N)]
    W_mp = [[0.0]*N for _ in range(N)]
    for i in range(N):
        W_ms[i][i] = 0.0
        W_mp[i][i] = 1.0
    for _ in range(M):
        parts = input().split()
        u, v, w = int(parts[0])-1, int(parts[1])-1, float(parts[2])
        if w < W_ms[u][v]: W_ms[u][v] = w
        if w > W_mp[u][v]: W_mp[u][v] = w

    def dijkstra_minsum(src):
        dist = [INF]*N; dist[src] = 0
        hq = [(0, src)]
        while hq:
            d, u = heapq.heappop(hq)
            if d > dist[u]: continue
            for v in range(N):
                if W_ms[u][v] != INF and dist[u] + W_ms[u][v] < dist[v]:
                    dist[v] = dist[u] + W_ms[u][v]
                    heapq.heappush(hq, (dist[v], v))
        return dist

    def dijkstra_maxprod(src):
        best = [0.0]*N; best[src] = 1.0
        hq = [(-1.0, src)]
        while hq:
            neg_d, u = heapq.heappop(hq)
            d = -neg_d
            if d < best[u]: continue
            for v in range(N):
                nb = best[u] * W_mp[u][v]
                if nb > best[v]:
                    best[v] = nb
                    heapq.heappush(hq, (-nb, v))
        return best

    Q = int(input())
    for _ in range(Q):
        parts = input().split()
        s = int(parts[0])-1
        qtype = parts[1]
        if qtype == 'min-sum':
            ans = dijkstra_minsum(s)
            print(*[f"{x:.0f}" if x != INF else "INF" for x in ans])
        else:
            ans = dijkstra_maxprod(s)
            print(*[f"{x:.6f}" for x in ans])

solve()

Step-by-Step 解説

Step 1: 代数的パス問題の統一枠組み

最短路問題は「パスの辺コストを $\otimes$ で組み合わせ、複数パスを $\oplus$ で比較する」操作として抽象化できる。半環の選択だけで異なる問題が解ける。

Step 2: 熱帯半環と Dijkstra の対応

熱帯半環 $(\mathbb{R}_{\ge 0} \cup \{+\infty\}, \min, +, +\infty, 0)$ 上の行列積が通常の最短路行列に対応。Dijkstra は隣接行列に対する単一始点版。

Step 3: max-product Dijkstra

辺重みを「確率」として解釈する場合、$-\log w$ に変換すれば min-sum 問題に帰着できる。直接 max-product Dijkstra も構成できる（辺重みが $\le 1$ かつ非負の場合）。

Step 4: 行列半環べき乗による一般解

$N$ 頂点グラフで $N$ 回の行列積（半環）を計算すれば全点対最短路に対応。$O(N^3)$ で Floyd-Warshall の代数的一般化。

よくあるミス

次のステップ

• 発展問題: 期待値の最短路（確率的グラフ・Bellman 方程式）
• 参考: Mohri (2002) "Semiring Frameworks and Algorithms for Shortest-Distance Problems"

自己評価