The algorithm solves the shortest path problem for each pair of node when the edges can have negative length but the graph should not contain cycles with negative sum of length. If we can assume that all edge is non-negative in the graph then the dijkstra algorithm should be used from each node.
The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap implementation is slower than either binary heap implementation or the Floyd-Warshall algorithm.
|
Public Types |
typedef _Traits::Graph | Graph |
| The type of the underlying graph.
|
typedef _Traits::LengthMap::Value | Value |
| The type of the length of the edges.
|
typedef _Traits::LengthMap | LengthMap |
| The type of the map that stores the edge lengths.
|
typedef _Traits::PredMap | PredMap |
| The type of the map that stores the last edges of the shortest paths. The type of the PredMap is a matrix map for Edges.
|
typedef _Traits::DistMap | DistMap |
| The type of the map that stores the dists of the nodes. The type of the DistMap is a matrix map for Values.
|
typedef _Traits::OperationTraits | OperationTraits |
| The operation traits.
|
typedef _Traits::HeapCrossRef | HeapCrossRef |
| The cross reference type used for the current heap.
|
typedef _Traits::Heap | Heap |
| The heap type used by the dijkstra algorithm.
|
Public Member Functions |
| Johnson (const Graph &_graph, const LengthMap &_length) |
| Constructor.
|
| ~Johnson () |
| Destructor.
|
Johnson & | lengthMap (const LengthMap &m) |
| Sets the length map.
|
Johnson & | predMap (PredMap &m) |
| Sets the map storing the predecessor edges.
|
Johnson & | distMap (DistMap &m) |
| Sets the map storing the distances calculated by the algorithm.
|
|
The simplest way to execute the algorithm is to use one of the member functions called run (...).
If you need more control on the execution, Finally start() will perform the actual path computation.
|
void | init () |
| Initializes the internal data structures.
|
template<typename PotentialMap> |
void | shiftedStart (const PotentialMap &potential) |
| Executes the algorithm with own potential map.
|
void | start () |
| Executes the algorithm.
|
bool | checkedStart () |
| Executes the algorithm and checks the negatvie cycles.
|
void | run () |
| Runs Johnson algorithm.
|
|
The result of the Johnson algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.
|
template<typename Path> |
bool | getPath (Path &p, Node source, Node target) |
| Copies the shortest path to t into p .
|
Value | dist (Node source, Node target) const |
| The distance between two nodes.
|
Edge | predEdge (Node root, Node node) const |
| Returns the 'previous edge' of the shortest path tree.
|
Node | predNode (Node root, Node node) const |
| Returns the 'previous node' of the shortest path tree.
|
const DistMap & | distMap () const |
| Returns a reference to the matrix node map of distances.
|
const PredMap & | predMap () const |
| Returns a reference to the shortest path tree map.
|
bool | connected (Node source, Node target) |
| Checks if a node is reachable from the root.
|
Classes |
struct | DefDistMap |
| Named parameter for setting DistMap type More...
|
struct | DefHeap |
| Named parameter for setting heap and cross reference type More...
|
struct | DefOperationTraits |
| Named parameter for setting OperationTraits type More...
|
struct | DefPredMap |
| Named parameter for setting PredMap type Named parameter for setting PredMap type More...
|
struct | DefStandardHeap |
class | UninitializedParameter |
| Exception for uninitialized parameters. More...
|