bellman_ford

ソースコード

from titan_pylib.graph.bellman_ford import bellman_ford

view on github

展開済みコード

 1# from titan_pylib.graph.bellman_ford import bellman_ford
 2from typing import Optional, Union
 3
 4
 5def bellman_ford(
 6    G: list[list[tuple[int, int]]], s: int, inf: Union[int, float] = float("inf")
 7) -> Optional[list[Union[int, float]]]:
 8    """Return dist from s. / O(nm)"""
 9    n = len(G)
10    dist = [inf] * n
11    dist[s] = 0
12    for _ in range(n):
13        update = 0
14        for v, e in enumerate(G):
15            for x, c in e:
16                if dist[v] != inf and dist[v] + c < dist[x]:
17                    dist[x] = dist[v] + c
18                    update = 1
19        if not update:
20            break
21    else:
22        return None  # NEGATIVE CYCLE
23    return dist

仕様

bellman_ford(G: list[list[tuple[int, int]]], s: int, inf: int | float = inf) → list[int | float] | None[source]

Return dist from s. / O(nm)