 # OpenGraph DrawingFramework

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.

## ◆ 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::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.
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, T maxLength = std::numeric_limits::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.
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, T maxLength = std::numeric_limits::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 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, T maxLength = std::numeric_limits::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 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
 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 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
 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 216 of file Dijkstra.h.

## ◆ 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: