bellmanFord
(expansion/graph/bellmanFord.py)

• View this file on GitHub
• Last update: 2023-07-06 22:40:04+09:00

概要

ベルマンフォードです．

$edges = [(from1, to1, cost1), (from2, to2, cost2), …)]$の形式で辺情報を与えてください

使い方

inf は十分に大きい値を適当に設定してください

dist = bellmanFord(n, edges, s, inf=1 << 60)

負閉路がある場合は None を返します．

Code

def bellmanFord(n, edges, s, inf=1 << 60):
    """
    edges = [(from1, to1, cost1), (from2, to2, cost2), ...)]
    """
    dist = [inf] * n
    dist[s] = 0

    for _ in range(n):
        update = False
        for u, v, d in edges:
            if dist[u] != inf and dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                update = True

        if not update:
            return dist

    return None

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page