Feature Request: Add Johnson’s Algorithm for All-Pairs Shortest Paths #13591
Description
Feature description
Description
Implement Johnson’s Algorithm to compute the shortest paths between all pairs of vertices in a weighted directed graph.
This algorithm efficiently combines Bellman-Ford and Dijkstra’s algorithms, allowing it to handle graphs with negative edge weights (but no negative cycles).
Johnson’s algorithm is particularly efficient for sparse graphs, making it a good complement to the Floyd–Warshall algorithm, which performs better on dense graphs.
Proposed Changes
- Add a new module or function:
johnson(graph) - Use Bellman-Ford for reweighting edges.
- Run Dijkstra’s algorithm for each vertex using the reweighted graph.
- Return a matrix or dictionary containing shortest path distances between all pairs of vertices.
Example Usage
graph = {
0: [(1, 3), (2, 8), (4, -4)],
1: [(3, 1), (4, 7)],
2: [(1, 4)],
3: [(0, 2), (2, -5)],
4: [(3, 6)]
}
distances = johnson(graph)
print(distances)Expected Output
A dictionary (or 2D array) showing the shortest distance between every pair of nodes.
Example:
{
0: {0: 0, 1: 1, 2: -3, 3: 2, 4: -4},
1: {0: 3, 1: 0, 2: -4, 3: 1, 4: -1},
2: {0: 7, 1: 4, 2: 0, 3: 5, 4: 3},
3: {0: 2, 1: -1, 2: -5, 3: 0, 4: -2},
4: {0: 8, 1: 5, 2: 1, 3: 6, 4: 0}
}Why This is Useful
Johnson’s algorithm provides an efficient way to handle sparse graphs with negative weights, which cannot be efficiently processed by standard Dijkstra’s algorithm.
It complements Floyd–Warshall for cases where the number of edges is much smaller than the number of vertex pairs.
This addition will enhance the repository’s collection of shortest path algorithms, providing a more complete algorithmic toolkit.
Additional Notes
- Include error handling for graphs with negative weight cycles (detected via Bellman-Ford).
- Add unit tests to verify correctness against known graph cases.
- Document time complexity analysis and include explanation in the docstring.
References
- Cormen et al., Introduction to Algorithms (CLRS), 3rd Edition, Chapter 25.
- Wikipedia – Johnson’s algorithm