cpl/graph/bellman_ford.py

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00

Code

from typing import List

from cpl import INF
from cpl.graph import WeightedAdjList


def bellman_ford(graph: WeightedAdjList, start: int) -> List[int]:
    N = len(graph)
    cost = [INF] * N
    cost[start] = 0

    for i in range(N):
        is_intact = True
        for v in range(N):
            if cost[v] == INF:
                continue
            for nv, nw in graph[v]:
                if (nc := cost[v] + nw) >= cost[nv]:
                    continue
                cost[nv] = nc
                is_intact = False
                if i == N - 1:
                    return []
        if is_intact:
            break
    return cost

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.9.2/x64/lib/python3.9/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.9.2/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError