ベルマンフォード法
(Graph/ShortestPath/bellman_ford.py)

• View this file on GitHub
• Last update: 2021-01-05 04:12:38+09:00

概要

重み付き有向グラフにおける単一始点最短経路問題を解くアルゴリズム。各辺の重みは負でもよい。

使い方

bellman_ford(start: int, graph: Sequence[Iterable[Tuple[int, int]]]) -> Tuple[bool, List[int]]
$G = (V, E)$ で表される重み付き有向グラフ graph に対して、始点 start からすべての頂点への最短距離を求める。始点からたどり着ける負閉路が存在しないときは True と最短距離のリストを返す。一方で、始点からたどり着ける負閉路が存在するときは False と要素未定義のリストを返す。計算量 $O(VE)$

Verified with

• TestCase/AOJ/GRL_1_B.test.py

Code

def bellman_ford(start, graph):
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    for _ in range(n):
        update = False
        for v, edges in enumerate(graph):
            for nxt_v, cost in edges:
                if dist[v] != INF and dist[nxt_v] > dist[v] + cost:
                    dist[nxt_v] = dist[v] + cost
                    update = True
        if not update:
            break
    else:
        return True, dist  # startから辿り着ける負閉路が存在
    return False, dist  # startから辿り着ける負閉路が存在しない

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/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.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page