graph::shortest_path::SPFA Class Reference

#include <SPFA.hpp>

Static Public Member Functions
template<typename TGraph , typename TNode , typename F = std::function<void(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 &) -> void {})
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)

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::SPFA::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 SPFA 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 negative cycle

Here is the call graph for this function:

Here is the caller 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::SPFA::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::SPFA::run ( const TGraph &  graph, const TNode &  start, F  f_user = [](const TNode &,                    const typename TGraph::edge_type::weight_type &) -> void {}  )

static

Run SPFA 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).

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 negative cycle.

Here is the call graph for this function:

---

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

• alib2graph_algo/src/shortest_path/SPFA.hpp