graphs.johnson
==============

.. py:module:: graphs.johnson


Attributes
----------

.. autoapisummary::

   graphs.johnson.Node
   graphs.johnson.adjacency
   graphs.johnson.edge


Functions
---------

.. autoapisummary::

   graphs.johnson._bellman_ford
   graphs.johnson._collect_nodes_and_edges
   graphs.johnson._dijkstra
   graphs.johnson.johnson


Module Contents
---------------

.. py:function:: _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.


.. py:function:: _collect_nodes_and_edges(graph: adjacency) -> tuple[list[Node], list[edge]]

.. py:function:: _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.


.. py:function:: 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


.. py:data:: Node

.. py:data:: adjacency

.. py:data:: edge