Dijkstra over reweighted graph, using potentials h to make weights non-negative. Returns distances from start in the reweighted space.
(
start: Node,
nodes: list[Node],
graph: adjacency,
potentials: dict[Node, float],
)
| 41 | |
| 42 | |
| 43 | def _dijkstra( |
| 44 | start: Node, |
| 45 | nodes: list[Node], |
| 46 | graph: adjacency, |
| 47 | potentials: dict[Node, float], |
| 48 | ) -> dict[Node, float]: |
| 49 | """ |
| 50 | Dijkstra over reweighted graph, using potentials h to make weights non-negative. |
| 51 | Returns distances from start in the reweighted space. |
| 52 | """ |
| 53 | inf = float("inf") |
| 54 | dist: dict[Node, float] = dict.fromkeys(nodes, inf) |
| 55 | dist[start] = 0.0 |
| 56 | heap: list[tuple[float, Node]] = [(0.0, start)] |
| 57 | |
| 58 | while heap: |
| 59 | d_u, u = heapq.heappop(heap) |
| 60 | if d_u > dist[u]: |
| 61 | continue |
| 62 | for v, w in graph.get(u, []): |
| 63 | w_prime = w + potentials[u] - potentials[v] |
| 64 | if w_prime < 0: |
| 65 | raise ValueError( |
| 66 | "Negative edge weight after reweighting: numeric error" |
| 67 | ) |
| 68 | new_dist = d_u + w_prime |
| 69 | if new_dist < dist[v]: |
| 70 | dist[v] = new_dist |
| 71 | heapq.heappush(heap, (new_dist, v)) |
| 72 | return dist |
| 73 | |
| 74 | |
| 75 | def johnson(graph: adjacency) -> dict[Node, dict[Node, float]]: |