pub fn johnson<A, W, Ty>(
graph: &BaseGraph<A, W, Ty>,
) -> Option<NodeMap<NodeMap<Option<W>>>>where
W: Copy + PartialOrd + Add<Output = W> + Sub<Output = W> + From<u8> + Ord,
Ty: GraphConstructor<A, W>,Expand description
§============================ Johnson’s Algorithm
Computes all‑pairs shortest paths for sparse graphs (even with negative edge weights)
by reweighting the graph to eliminate negatives and then running Dijkstra’s algorithm from each node.
Returns Some(map) if no negative cycle is detected, or None otherwise.
§Complexity
- Time: O(VE \log V) (implementation uses a binary heap)
- Space: O(V^2)