Johnson.H File Reference

Johnson's algorithm for all-pairs shortest paths. More...

#include <Dijkstra.H>
#include <Bellman_Ford.H>
#include <tpl_graph.H>
#include <tpl_dynList.H>
#include <ah-errors.H>
#include <limits>
#include <type_traits>

Include dependency graph for Johnson.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Johnson< GT, Distance, Ait, NAit, SA >
	Johnson's algorithm for all-pairs shortest paths. More...
struct	Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Reweighted_Dist

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Johnson's algorithm for all-pairs shortest paths.

Implements Johnson's algorithm combining Bellman-Ford and Dijkstra for finding all-pairs shortest paths in sparse graphs, including graphs with negative edge weights. O(V²log V + VE) complexity.

Algorithm Overview

Johnson's algorithm works in the following steps:

1. Add a dummy node q connected to all other nodes with zero-weight edges
2. Run Bellman-Ford from q to compute node potentials h(v)
3. Reweight all edges: w'(u,v) = w(u,v) + h(u) - h(v)
4. For each source, run Dijkstra on the reweighted graph
5. Adjust distances back: d(s,t) = d'(s,t) - h(s) + h(t)

Complexity

Phase	Time
Bellman-Ford	O(VE)
V × Dijkstra	O(V(V log V + E))
Total	O(V² log V + VE)

For sparse graphs (E = O(V)), this is O(V² log V), better than Floyd-Warshall's O(V³).

Author

Leandro Rabindranath León

Definition in file Johnson.H.