cp_library/alg/graph/bellman_ford_neg_cyc_check_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/alg/graph/bellman_ford_fn.py

Verified with

• test/aoj/grl/grl_1_b_bellman_ford.test.py

Code

import cp_library.alg.graph.__header__
from math import inf

def bellman_ford(G, N, root) -> tuple[bool, list[int]]:
    from cp_library.alg.graph.bellman_ford_fn import bellman_ford
    D = bellman_ford(G, N, root)
    neg_cycle = any(D[u]+w<D[v] for u, edges in enumerate(G) for v,w in edges if D[u] != inf)
    return neg_cycle, D

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from math import inf

def bellman_ford(G, N, root) -> tuple[bool, list[int]]:
    
    def bellman_ford(G, N, root) -> list[int]:
        D = [inf]*N
        D[root] = 0
        for _ in range(N-1):
            for u, edges in enumerate(G):
                if D[u] == inf: continue
                for v,w in edges:
                    D[v] = min(D[v], D[u] + w)
        return D
    D = bellman_ford(G, N, root)
    neg_cycle = any(D[u]+w<D[v] for u, edges in enumerate(G) for v,w in edges if D[u] != inf)
    return neg_cycle, D

Back to top page