Source code for titan_pylib.graph.bellman_ford

 1from typing import Optional, Union
 2
 3

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