spfa

ソースコード

from titan_pylib.graph.spfa import spfa

view on github

展開済みコード

 1# from titan_pylib.graph.spfa import spfa
 2from collections import deque
 3
 4inf = float("inf")
 5
 6
 7# O(VE)
 8# 負のコストでもよい
 9# ベルマンフォードより高速かもしれない
10def spfa(G, s):
11    n = len(G)
12    now = [0] * n
13    dist = [inf] * n
14    dq = deque([s])
15    dist[s] = 0
16    now[s] = 1
17    cnt = [0] * n
18    cnt[s] = 1
19    while dq:
20        v = dq.pop()
21        now[v] = 0
22        d = dist[v]
23        for x, c in G[v]:
24            if dist[x] > d + c:
25                dist[x] = d + c
26                if not now[x]:
27                    cnt[x] += 1
28                    if n <= cnt[x]:
29                        return None
30                    if dq and d + c < dq[0]:
31                        dq.appendleft(x)
32                    else:
33                        dq.append(x)
34                    now[x] = 1
35    return dist

仕様

spfa(G, s)[source]