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 60 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, T  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

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

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 253 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, T  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

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

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 276 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, T  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

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 145 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, T  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

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 233 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

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 77 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

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

---

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

• include/ogdf/graphalg/Dijkstra.h