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)

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 53 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 246 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 269 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 138 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 226 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 70 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 207 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 55 of file Dijkstra.h.

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

include/ogdf/graphalg/Dijkstra.h

OpenGraph DrawingFramework

Public Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ call() [1/2]

◆ call() [2/2]

◆ callBound() [1/2]

◆ callBound() [2/2]

◆ callUnbound() [1/2]

◆ callUnbound() [2/2]

Member Data Documentation

◆ m_eps

Open
Graph Drawing
Framework