Source code for titan_pylib.graph.spfa

 1from collections import deque
 2
 3inf = float("inf")
 4
 5
 6# O(VE)
 7# 負のコストでもよい
 8# ベルマンフォードより高速かもしれない

[docs]
 9def spfa(G, s):
10    n = len(G)
11    now = [0] * n
12    dist = [inf] * n
13    dq = deque([s])
14    dist[s] = 0
15    now[s] = 1
16    cnt = [0] * n
17    cnt[s] = 1
18    while dq:
19        v = dq.pop()
20        now[v] = 0
21        d = dist[v]
22        for x, c in G[v]:
23            if dist[x] > d + c:
24                dist[x] = d + c
25                if not now[x]:
26                    cnt[x] += 1
27                    if n <= cnt[x]:
28                        return None
29                    if dq and d + c < dq[0]:
30                        dq.appendleft(x)
31                    else:
32                        dq.append(x)
33                    now[x] = 1
34    return dist