Bellman-Ford relaxation to compute potentials h[v] for all vertices. Raises ValueError if a negative weight cycle exists.
(nodes: list[Node], edges: list[edge])
| 18 | |
| 19 | |
| 20 | def _bellman_ford(nodes: list[Node], edges: list[edge]) -> dict[Node, float]: |
| 21 | """ |
| 22 | Bellman-Ford relaxation to compute potentials h[v] for all vertices. |
| 23 | Raises ValueError if a negative weight cycle exists. |
| 24 | """ |
| 25 | dist: dict[Node, float] = dict.fromkeys(nodes, 0.0) |
| 26 | n = len(nodes) |
| 27 | |
| 28 | for _ in range(n - 1): |
| 29 | updated = False |
| 30 | for u, v, w in edges: |
| 31 | if dist[u] + w < dist[v]: |
| 32 | dist[v] = dist[u] + w |
| 33 | updated = True |
| 34 | if not updated: |
| 35 | break |
| 36 | else: |
| 37 | for u, v, w in edges: |
| 38 | if dist[u] + w < dist[v]: |
| 39 | raise ValueError("Negative weight cycle detected") |
| 40 | return dist |
| 41 | |
| 42 | |
| 43 | def _dijkstra( |