Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::Dijkstra< T, H > Class Template Reference

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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 

Protected Attributes

EpsilonTest m_eps
 For floating point comparisons (if floating point is used) More...
 

Detailed Description

template<typename T, template< typename P, class C > class H = PairingHeap>
class ogdf::Dijkstra< T, H >

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 54 of file Dijkstra.h.

Member Function Documentation

◆ call() [1/2]

template<typename T , template< typename P, class C > class H = PairingHeap>
void ogdf::Dijkstra< T, H >::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,
maxLength = std::numeric_limits<T>::max() 
)
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.

Parameters
GThe original input graph
weightThe edge weights
sourcesA list of source nodes
predecessorThe resulting predecessor relation
distanceThe resulting distances to all other nodes
directedTrue iff G should be interpreted as a directed graph
arcsReversedTrue if the arcs should be followed in reverse. It has only an effect when setting directed to true
targetA target node. Terminate once the shortest path to this node is found
maxLengthUpper bound on path length
Note
If no target or maximum distance is given, use the unbound algorithm that runs faster on most instances. On some types of instances (especially sparse ones) the bound algorithm tends to run faster. To force its usage, use the callBound method directly.
See also
callBound(const Graph&, const EdgeArray<T>&, const List<node>&, NodeArray<edge>&, NodeArray<T>&, bool, node, T)

Definition at line 267 of file Dijkstra.h.

◆ call() [2/2]

template<typename T , template< typename P, class C > class H = PairingHeap>
void ogdf::Dijkstra< T, H >::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,
maxLength = std::numeric_limits<T>::max() 
)
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.

Parameters
GThe original input graph
weightThe edge weights
sThe source node
predecessorThe resulting predecessor relation
distanceThe resulting distances to all other nodes
directedTrue iff G should be interpreted as a directed graph
arcsReversedTrue if the arcs should be followed in reverse. It has only an effect when setting directed to true
targetA target node. Terminate once the shortest path to this node is found
maxLengthUpper bound on path length
Note
If no target or maximum distance is given, use the unbound algorithm that runs faster on most instances. On some types of instances (especially sparse ones) the bound algorithm tends to run faster. To force its usage, use the callBound method directly.
See also
callBound(const Graph&, const EdgeArray<T>&, node, NodeArray<edge>&, NodeArray<T>&, bool, node, T)

Definition at line 296 of file Dijkstra.h.

◆ callBound() [1/2]

template<typename T , template< typename P, class C > class H = PairingHeap>
void ogdf::Dijkstra< T, H >::callBound ( const Graph G,
const EdgeArray< T > &  weight,
const List< node > &  sources,
NodeArray< edge > &  predecessor,
NodeArray< T > &  distance,
bool  directed,
bool  arcsReversed,
node  target,
maxLength = std::numeric_limits<T>::max() 
)
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.

Parameters
GThe original input graph
weightThe edge weights
sourcesA list of source nodes
predecessorThe resulting predecessor relation
distanceThe resulting distances to all other nodes
directedTrue iff G should be interpreted as a directed graph
arcsReversedTrue if the arcs should be followed in reverse. It has only an effect when setting directed to true
targetA target node. Terminate once the shortest path to this node is found
maxLengthUpper bound on path length

Definition at line 142 of file Dijkstra.h.

◆ callBound() [2/2]

template<typename T , template< typename P, class C > class H = PairingHeap>
void ogdf::Dijkstra< T, H >::callBound ( const Graph G,
const EdgeArray< T > &  weight,
node  s,
NodeArray< edge > &  predecessor,
NodeArray< T > &  distance,
bool  directed,
bool  arcsReversed,
node  target,
maxLength = std::numeric_limits<T>::max() 
)
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.

Parameters
GThe original input graph
weightThe edge weights
sThe source node
predecessorThe resulting predecessor relation
distanceThe resulting distances to all other nodes
directedTrue iff G should be interpreted as a directed graph
arcsReversedTrue if the arcs should be followed in reverse. It has only an effect when setting directed to true
targetA target node. Terminate once the shortest path to this node is found
maxLengthUpper bound on path length

Definition at line 241 of file Dijkstra.h.

◆ callUnbound() [1/2]

template<typename T , template< typename P, class C > class H = PairingHeap>
void ogdf::Dijkstra< T, H >::callUnbound ( const Graph G,
const EdgeArray< T > &  weight,
const List< node > &  sources,
NodeArray< edge > &  predecessor,
NodeArray< T > &  distance,
bool  directed = false,
bool  arcsReversed = false 
)
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.

Parameters
GThe original input graph
weightThe edge weights
sourcesA list of source nodes
predecessorThe resulting predecessor relation
distanceThe resulting distances to all other nodes
directedTrue iff G should be interpreted as a directed graph
arcsReversedTrue if the arcs should be followed in reverse. It has only an effect when setting directed to true

Definition at line 71 of file Dijkstra.h.

◆ callUnbound() [2/2]

template<typename T , template< typename P, class C > class H = PairingHeap>
void ogdf::Dijkstra< T, H >::callUnbound ( const Graph G,
const EdgeArray< T > &  weight,
node  s,
NodeArray< edge > &  predecessor,
NodeArray< T > &  distance,
bool  directed = false,
bool  arcsReversed = false 
)
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.

Parameters
GThe original input graph
weightThe edge weights
sThe source node
predecessorThe resulting predecessor relation
distanceThe resulting distances to all other nodes
directedTrue iff G should be interpreted as a directed graph
arcsReversedTrue if the arcs should be followed in reverse. It has only an effect when setting directed to true

Definition at line 216 of file Dijkstra.h.

Member Data Documentation

◆ m_eps

template<typename T , template< typename P, class C > class H = PairingHeap>
EpsilonTest ogdf::Dijkstra< T, H >::m_eps
protected

For floating point comparisons (if floating point is used)

Definition at line 56 of file Dijkstra.h.


The documentation for this class was generated from the following file: