graphs.johnson

Attributes

Node
adjacency
edge

Functions

_bellman_ford(→ dict[Node, float])	Bellman-Ford relaxation to compute potentials h[v] for all vertices.
_collect_nodes_and_edges(→ tuple[list[Node], list[edge]])
_dijkstra(→ dict[Node, float])	Dijkstra over reweighted graph, using potentials h to make weights non-negative.
johnson(→ dict[Node, dict[Node, float]])	Compute all-pairs shortest paths using Johnson's algorithm.

Module Contents

graphs.johnson._bellman_ford(nodes: list[Node], edges: list[edge]) → dict[Node, float]

Bellman-Ford relaxation to compute potentials h[v] for all vertices. Raises ValueError if a negative weight cycle exists.

graphs.johnson._collect_nodes_and_edges(graph: adjacency) → tuple[list[Node], list[edge]]

graphs.johnson._dijkstra(start: Node, nodes: list[Node], graph: adjacency, potentials: dict[Node, float]) → dict[Node, float]

Dijkstra over reweighted graph, using potentials h to make weights non-negative. Returns distances from start in the reweighted space.

graphs.johnson.johnson(graph: adjacency) → dict[Node, dict[Node, float]]

Compute all-pairs shortest paths using Johnson’s algorithm.

Reference:

https://en.wikipedia.org/wiki/Johnson%27s_algorithm

Args:

graph: adjacency list {u: [(v, weight), …], …}

Returns:

dict of dicts: dist[u][v] = shortest distance from u to v

Raises:

ValueError: if a negative weight cycle is detected

Example: >>> g = { … 0: [(1, 3), (2, 8), (4, -4)], … 1: [(3, 1), (4, 7)], … 2: [(1, 4)], … 3: [(0, 2), (2, -5)], … 4: [(3, 6)], … } >>> round(johnson(g)[0][3], 2) 2.0

graphs.johnson.Node

graphs.johnson.adjacency

graphs.johnson.edge