gl::algorithm::Dijkstra< Graph > Class Template Reference

Class that computes Dijkstra's Shortest Paths algorithm. More...

#include <Dijkstra.hpp>

Public Member Functions
	Dijkstra (const Graph graph)
	Initialized Constructor. More...
	Dijkstra ()
	Default constructor. More...
	Dijkstra (const Dijkstra &)=default
	Copy constructor. More...
	Dijkstra (Dijkstra &&) noexcept=default
	Move constructor. More...
Dijkstra &	operator= (const Dijkstra &)=default
	Copy assignment. More...
Dijkstra &	operator= (Dijkstra &&) noexcept=default
	Move assignment. More...
	~Dijkstra ()=default
	Default destructor. More...
Distance< val_t >	pathLength (const idx_t src, const idx_t dest)
std::pair< bool, typename Graph::idx_list_t >	getPath (const idx_t src, const idx_t dest)
	Computes the node sequence that represents the shortest path from src to dest. More...
Graph	getSPT (const idx_t src)
	Returns a graph that only contains the edges of the SPT (Shortest Path Tree) More...
void	initialize (const Graph graph)
	Initializes the algorithm with a new Graph. More...

Private Types
using	idx_t = typename Graph::idx_t
using	val_t = typename Graph::val_t
using	pair_t = std::pair< Distance< val_t >, idx_t >
using	result_t = std::vector< pair_t >

Private Member Functions
void	compute (const idx_t src)
	Computation. This is where the shortest distances and the predecessors of each node on the shortest path tree get computed. More...

Private Attributes
bool	isInitializedWithGraph_
	Boolean indicating whether the class has been initialized with a Graph. More...
std::vector< bool >	isInitializedWithSource_
	Boolean vector indicating whether the node whose ID corresponds to an element in the vector had its shortest path tree computed. More...
Graph	graph_
	Source Graph. More...
std::vector< Graph >	result_
	SPT graph. More...
std::vector< result_t >	final_
	Shortest Path lengths & predecessors. More...

Detailed Description

template<class Graph>
class gl::algorithm::Dijkstra< Graph >

Class that computes Dijkstra's Shortest Paths algorithm.

Member Typedef Documentation

template<class Graph >

using gl::algorithm::Dijkstra< Graph >::idx_t = typename Graph::idx_t

private

template<class Graph >

using gl::algorithm::Dijkstra< Graph >::val_t = typename Graph::val_t

private

template<class Graph >

using gl::algorithm::Dijkstra< Graph >::pair_t = std::pair<Distance<val_t>,idx_t>

private

template<class Graph >

using gl::algorithm::Dijkstra< Graph >::result_t = std::vector<pair_t>

private

Constructor & Destructor Documentation

template<class Graph >

gl::algorithm::Dijkstra< Graph >::Dijkstra ( const Graph  graph )

explicit

Initialized Constructor.

This constructor takes a graph argument, ready for usage.

Parameters

[in]

graph

Graph that will be traversedConstructor with Graph included

template<class Graph >

gl::algorithm::Dijkstra< Graph >::Dijkstra

(

)

Default constructor.

template<class Graph >

gl::algorithm::Dijkstra< Graph >::Dijkstra ( const Dijkstra< Graph > &  )

default

Copy constructor.

template<class Graph >

gl::algorithm::Dijkstra< Graph >::Dijkstra ( Dijkstra< Graph > &&  )

defaultnoexcept

Move constructor.

template<class Graph >

gl::algorithm::Dijkstra< Graph >::~Dijkstra ( )

default

Default destructor.

Member Function Documentation

template<class Graph >

Dijkstra& gl::algorithm::Dijkstra< Graph >::operator= ( const Dijkstra< Graph > &  )

default

Copy assignment.

template<class Graph >

Dijkstra& gl::algorithm::Dijkstra< Graph >::operator= ( Dijkstra< Graph > &&  )

defaultnoexcept

Move assignment.

template<class Graph >

gl::Distance< typename Graph::val_t > gl::algorithm::Dijkstra< Graph >::pathLength	(	const idx_t	src,
		const idx_t	dest
	)

template<class Graph >

std::pair< bool, typename Graph::idx_list_t > gl::algorithm::Dijkstra< Graph >::getPath	(	const idx_t	src,
		const idx_t	dest
	)

Computes the node sequence that represents the shortest path from src to dest.

Parameters

[in]	src	Start of shortest path
[in]	dest	End of shortest path

Returns

shortest path in form of an ordered list of node indices.

template<class Graph >

Graph gl::algorithm::Dijkstra< Graph >::getSPT

(

const idx_t

src

)

Returns a graph that only contains the edges of the SPT (Shortest Path Tree)

Parameters

[in]

src

Node whose SPT is to be known

Returns

SPT Graph.

template<class Graph >

void gl::algorithm::Dijkstra< Graph >::initialize

(

const Graph

graph

)

Initializes the algorithm with a new Graph.

Parameters

[in]

graph

Graph storing information for the Shortest Path Algorithm

template<class Graph >

void gl::algorithm::Dijkstra< Graph >::compute ( const idx_t  src )

private

Computation. This is where the shortest distances and the predecessors of each node on the shortest path tree get computed.

Parameters

[in]

src

Source node. All shortest paths will be computed from here.

Member Data Documentation

template<class Graph >

bool gl::algorithm::Dijkstra< Graph >::isInitializedWithGraph_

private

Boolean indicating whether the class has been initialized with a Graph.

template<class Graph >

std::vector<bool> gl::algorithm::Dijkstra< Graph >::isInitializedWithSource_

private

Boolean vector indicating whether the node whose ID corresponds to an element in the vector had its shortest path tree computed.

template<class Graph >

Graph gl::algorithm::Dijkstra< Graph >::graph_

private

Source Graph.

template<class Graph >

std::vector<Graph> gl::algorithm::Dijkstra< Graph >::result_

private

SPT graph.

template<class Graph >

std::vector<result_t> gl::algorithm::Dijkstra< Graph >::final_

private

Shortest Path lengths & predecessors.

---

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

• /home/travis/build/guetzli32/GraphLib/graphlib/src/algorithms/Dijkstra.hpp