Dijkstra's single source shortest path algorithm. More...
#include <ogdf/graphalg/Dijkstra.h>
Public Member Functions  
void  call (const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max()) 
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths and distances to all other nodes by Dijkstra's algorithm.  
void  call (const Graph &G, const EdgeArray< T > &weight, const node s, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max()) 
Calculates, based on the graph G with corresponding edge costs and a source node s, the shortest paths and distances to all other nodes by Dijkstra's algorithm.  
void  callBound (const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed, bool arcsReversed, node target, T maxLength=std::numeric_limits< T >::max()) 
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths and distances to all other nodes by Dijkstra's algorithm.  
void  callBound (const Graph &G, const EdgeArray< T > &weight, node s, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed, bool arcsReversed, node target, T maxLength=std::numeric_limits< T >::max()) 
Calculates, based on the graph G with corresponding edge costs and a source node s, the shortest paths and distances to all other nodes by Dijkstra's algorithm.  
void  callUnbound (const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false) 
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths and distances to all other nodes by Dijkstra's algorithm.  
void  callUnbound (const Graph &G, const EdgeArray< T > &weight, node s, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false) 
Calculates, based on the graph G with corresponding edge costs and a source node s, the shortest paths and distances to all other nodes by Dijkstra's algorithm.  
Protected Attributes  
EpsilonTest  m_eps 
For floating point comparisons (if floating point is used)  
Dijkstra's single source shortest path algorithm.
This class implements Dijkstra's algorithm for computing single source shortest path in (undirected or directed) graphs with proper, positive edge weights. It returns a predecessor array as well as the shortest distances from the source node(s) to all others. It optionally supports early termination if only the shortest path to a specific node is required, or the maximum path length is to be limited.
Definition at line 53 of file Dijkstra.h.

inline 
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths and distances to all other nodes by Dijkstra's algorithm.
G  The original input graph 
weight  The edge weights 
sources  A list of source nodes 
predecessor  The resulting predecessor relation 
distance  The resulting distances to all other nodes 
directed  True iff G should be interpreted as a directed graph 
arcsReversed  True if the arcs should be followed in reverse. It has only an effect when setting directed to true 
target  A target node. Terminate once the shortest path to this node is found 
maxLength  Upper bound on path length 
callBound
method directly.Definition at line 246 of file Dijkstra.h.

inline 
Calculates, based on the graph G with corresponding edge costs and a source node s, the shortest paths and distances to all other nodes by Dijkstra's algorithm.
G  The original input graph 
weight  The edge weights 
s  The source node 
predecessor  The resulting predecessor relation 
distance  The resulting distances to all other nodes 
directed  True iff G should be interpreted as a directed graph 
arcsReversed  True if the arcs should be followed in reverse. It has only an effect when setting directed to true 
target  A target node. Terminate once the shortest path to this node is found 
maxLength  Upper bound on path length 
callBound
method directly.Definition at line 269 of file Dijkstra.h.

inline 
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths and distances to all other nodes by Dijkstra's algorithm.
Allows to specify a target node and maximum distance, after reaching which the algorithm will terminate early.
This implementation is different from the implementation of callUnbound() as runtime tests have shown the additional checks to increase run time for the basic use case.
G  The original input graph 
weight  The edge weights 
sources  A list of source nodes 
predecessor  The resulting predecessor relation 
distance  The resulting distances to all other nodes 
directed  True iff G should be interpreted as a directed graph 
arcsReversed  True if the arcs should be followed in reverse. It has only an effect when setting directed to true 
target  A target node. Terminate once the shortest path to this node is found 
maxLength  Upper bound on path length 
Definition at line 138 of file Dijkstra.h.

inline 
Calculates, based on the graph G with corresponding edge costs and a source node s, the shortest paths and distances to all other nodes by Dijkstra's algorithm.
Allows to specify a target node and maximum distance, after reaching which the algorithm will terminate early.
This implementation is different from the implementation of callUnbound() as runtime tests have shown the additional checks to increase run time for the basic use case.
G  The original input graph 
weight  The edge weights 
s  The source node 
predecessor  The resulting predecessor relation 
distance  The resulting distances to all other nodes 
directed  True iff G should be interpreted as a directed graph 
arcsReversed  True if the arcs should be followed in reverse. It has only an effect when setting directed to true 
target  A target node. Terminate once the shortest path to this node is found 
maxLength  Upper bound on path length 
Definition at line 226 of file Dijkstra.h.

inline 
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths and distances to all other nodes by Dijkstra's algorithm.
G  The original input graph 
weight  The edge weights 
sources  A list of source nodes 
predecessor  The resulting predecessor relation 
distance  The resulting distances to all other nodes 
directed  True iff G should be interpreted as a directed graph 
arcsReversed  True if the arcs should be followed in reverse. It has only an effect when setting directed to true 
Definition at line 70 of file Dijkstra.h.

inline 
Calculates, based on the graph G with corresponding edge costs and a source node s, the shortest paths and distances to all other nodes by Dijkstra's algorithm.
G  The original input graph 
weight  The edge weights 
s  The source node 
predecessor  The resulting predecessor relation 
distance  The resulting distances to all other nodes 
directed  True iff G should be interpreted as a directed graph 
arcsReversed  True if the arcs should be followed in reverse. It has only an effect when setting directed to true 
Definition at line 207 of file Dijkstra.h.

protected 
For floating point comparisons (if floating point is used)
Definition at line 55 of file Dijkstra.h.