cp_library/alg/graph/bellman_ford_fn.py

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

Required by

• cp_library/alg/graph/bellman_ford_neg_cyc_check_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) -> 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

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

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

Back to top page