Function johnson

graphs/johnson.py:75–118

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 Rais

(graph: adjacency)

def 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
    """
    nodes, edges = _collect_nodes_and_edges(graph)
    potentials = _bellman_ford(nodes, edges)

    all_pairs: dict[Node, dict[Node, float]] = {}
    inf = float("inf")
    for s in nodes:
        dist_reweighted = _dijkstra(s, nodes, graph, potentials)
        dists_orig: dict[Node, float] = {}
        for v in nodes:
            d_prime = dist_reweighted[v]
            if d_prime < inf:
                dists_orig[v] = d_prime - potentials[s] + potentials[v]
            else:
                dists_orig[v] = inf
        all_pairs[s] = dists_orig

    return all_pairs