graph::shortest_path::Dijkstra Class Reference

#include <Dijkstra.hpp>

Static Public Member Functions
template<typename TGraph , typename TNode , typename F = std::function<bool(const TNode &, const typename TGraph::edge_type::weight_type &)>>
static void	run (const TGraph &graph, const TNode &start, F f_user=[](const TNode &, const typename TGraph::edge_type::weight_type &) -> bool { return false;})
template<typename TGraph , typename TNode , typename F = std::function<void(const TNode &, const typename TGraph::edge_type::weight_type &)>>
static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type >	findPath (const TGraph &graph, const TNode &start, const TNode &goal, F f_user=[](const TNode &, const typename TGraph::edge_type::weight_type &) {})
template<typename TGraph , typename TNode >
static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type >	findPathRegistration (const TGraph &graph, const TNode &start, const TNode &goal)
template<typename TGraph , typename TNode , typename F = std::function<void(const TNode &, const typename TGraph::edge_type::weight_type &)>>
static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type >	findPathBidirectional (const TGraph &graph, const TNode &start, const TNode &goal, F f_user=[](const TNode &, const typename TGraph::edge_type::weight_type &) {})
template<typename TGraph , typename TNode >
static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type >	findPathBidirectionalRegistration (const TGraph &graph, const TNode &start, const TNode &goal)

Member Function Documentation

findPath()

template<typename TGraph , typename TNode , typename F >

ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type > graph::shortest_path::Dijkstra::findPath ( const TGraph &  graph, const TNode &  start, const TNode &  goal, F  f_user = [](const TNode &,                         const typename TGraph::edge_type::weight_type &) {}  )

static

Find the shortest path using Dijkstra algorithm from the start node to the goal node in the graph.

Whenever node is opened, f_user is called with two parameters (the opened node and value of currently shortest path).

Parameters

graph	to explore.
start	initial node.
goal	final node.
f_user	function which is called for every open node with value of currently shortest path.

Returns

pair where first := shortest path := distance of path, if there is no such path vector is empty and distance std::numeric_limits<edge_type:weight_type>::max().

Note

TEdge of graph must follow graph::edge::WeightedEdge interface.

See also

graph::edge_type::WeightedEdge.

Exceptions

std::out_of_range

if graph contains an edge with a negative weight.

Here is the call graph for this function:

Here is the caller graph for this function:

findPathBidirectional()

template<typename TGraph , typename TNode , typename F >

ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type > graph::shortest_path::Dijkstra::findPathBidirectional ( const TGraph &  graph, const TNode &  start, const TNode &  goal, F  f_user = [](const TNode &,                                      const typename TGraph::edge_type::weight_type &) {}  )

static

Find the shortest path using Dijkstra algorithm from the start node to the goal node in the graph. This algorithm is run in both direction, from start and also from goal.

Whenever node is opened, f_user is called with two parameters (the opened node and value of currently shortest path).

Parameters

graph	to explore.
start	initial node.
goal	final node.
f_user	function which is called for every open node with value of currently shortest path.

Returns

pair where first := shortest path := distance of path, if there is no such path vector is empty and distance std::numeric_limits<edge_type:weight_type>::max().

Note

TEdge of graph must follow graph::edge::WeightedEdge interface.

See also

graph::edge_type::WeightedEdge.

Exceptions

std::out_of_range

if graph contains an edge with a negative weight.

Here is the call graph for this function:

Here is the caller graph for this function:

findPathBidirectionalRegistration()

template<typename TGraph , typename TNode >

static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type > graph::shortest_path::Dijkstra::findPathBidirectionalRegistration ( const TGraph &  graph, const TNode &  start, const TNode &  goal  )

inlinestatic

Here is the call graph for this function:

findPathRegistration()

template<typename TGraph , typename TNode >

static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type > graph::shortest_path::Dijkstra::findPathRegistration ( const TGraph &  graph, const TNode &  start, const TNode &  goal  )

inlinestatic

Here is the call graph for this function:

run()

template<typename TGraph , typename TNode , typename F >

void graph::shortest_path::Dijkstra::run ( const TGraph &  graph, const TNode &  start, F  f_user = [](const TNode &,                    const typename TGraph::edge_type::weight_type &) -> bool { return false; }  )

static

Run Dijkstra algorithm from the start node in the graph.

Whenever node is opened, f_user is called with two parameters (the opened node and value of currently shortest path). If return of f_user is true, then the algorithm is stopped.

Parameters

graph	to explore.
start	initial node.
f_user	function which is called for every opened node with value of currently shortest path.

Note

TEdge of graph must follow graph::edge::WeightedEdge interface.

See also

graph::edge_type::WeightedEdge.

Exceptions

std::out_of_range

if graph contains an edge with a negative weight.

Here is the call graph for this function:

---

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

• alib2graph_algo/src/shortest_path/Dijkstra.hpp