MRPT logo

mrpt::math::CDijkstra< TYPE_EDGES > Class Template Reference

The Dijkstra algorithm for finding the shortest path between a given source node in a (weighted) directed graph and all other nodes. More...

#include <mrpt/math/dijkstra.h>

List of all members.

Classes

struct  TDistance
struct  TPrevious

Public Types

typedef size_t TNodeID
 The type for node IDs.
typedef std::list< std::pair
< TNodeID, TNodeID > > 
TListEdges
 A list of edges used to describe a path on the graph.

Public Member Functions

 CDijkstra (const mrpt::math::CDirectedGraph< TYPE_EDGES > &graph, const TNodeID &source_node_ID, double(*functor_edge_weight)(const TYPE_EDGES &edge)=NULL)
 Constructor, which takes the input graph and executes the entire Dijkstra algorithm.
void getShortestPathTo (const TNodeID target_node_ID, TListEdges &out_path) const
 Returns the shortest path between the source node passed in the constructor and the given target node.

Static Public Attributes

static const TNodeID INVALID_TNODEID = static_cast<TNodeID>(-1)

Protected Attributes

std::map< TNodeID, TDistanced
std::map< TNodeID, TPreviousprevious
std::map< TNodeID, std::pair
< TNodeID, TNodeID > > 
previous_arcs
std::map< TNodeID, bool > visited
TNodeID m_source_node_ID


Detailed Description

template<typename TYPE_EDGES>
class mrpt::math::CDijkstra< TYPE_EDGES >

The Dijkstra algorithm for finding the shortest path between a given source node in a (weighted) directed graph and all other nodes.

The constructor takes as input the graph (the set of directed edges) computes all the needed data, then successive calls to "getShortestPathTo" return the paths very efficiently.

Graphs are represented by instances of (or classes derived from) mrpt::math::CDirectedGraph , and node's IDs are size_t values, although the type TNodeID is also provided for clarity.

See this page on the wiki for a complete example.

Definition at line 51 of file dijkstra.h.


Member Typedef Documentation

template<typename TYPE_EDGES >
typedef std::list<std::pair<TNodeID,TNodeID> > mrpt::math::CDijkstra< TYPE_EDGES >::TListEdges

A list of edges used to describe a path on the graph.

Definition at line 55 of file dijkstra.h.

template<typename TYPE_EDGES >
typedef size_t mrpt::math::CDijkstra< TYPE_EDGES >::TNodeID

The type for node IDs.

Definition at line 54 of file dijkstra.h.


Constructor & Destructor Documentation

template<typename TYPE_EDGES >
mrpt::math::CDijkstra< TYPE_EDGES >::CDijkstra ( const mrpt::math::CDirectedGraph< TYPE_EDGES > &  graph,
const TNodeID source_node_ID,
double(*)(const TYPE_EDGES &edge)  functor_edge_weight = NULL 
) [inline]

Constructor, which takes the input graph and executes the entire Dijkstra algorithm.

The graph is given by its directed edges with a class such as:

    map< pair<size_t,size_t>, TYPE_EDGES>   myGraph;

If a function "functor_edge_weight" is provided which returns the weight of any given edge, then it will be used. Otherwise, all edges will weight equally.

See also:
getShortestPathTo
Exceptions:
std::exception If the source nodeID is not found in the graph

Definition at line 99 of file dijkstra.h.

References ASSERT_, mrpt::math::CDijkstra< TYPE_EDGES >::d, mrpt::math::CDirectedGraph< TYPE_EDGES >::edges, mrpt::math::CDirectedGraph< TYPE_EDGES >::end(), mrpt::math::CDirectedGraph< TYPE_EDGES >::getAllNodes(), mrpt::math::CDirectedGraph< TYPE_EDGES >::getNeighborsOf(), MRPT_TRY_END, MRPT_TRY_START, mrpt::math::CDijkstra< TYPE_EDGES >::previous, mrpt::math::CDijkstra< TYPE_EDGES >::previous_arcs, THROW_EXCEPTION_CUSTOM_MSG1, and mrpt::math::CDijkstra< TYPE_EDGES >::visited.


Member Function Documentation

template<typename TYPE_EDGES >
void mrpt::math::CDijkstra< TYPE_EDGES >::getShortestPathTo ( const TNodeID  target_node_ID,
TListEdges out_path 
) const [inline]

Returns the shortest path between the source node passed in the constructor and the given target node.

The reconstructed path contains a list of arcs (all of them exist in the graph with the given direction), such as the the first edge starts at the origin passed in the constructor, and the last one contains the given target.

Note:
An empty list of edges is returned when target equals the source node.

Definition at line 198 of file dijkstra.h.

References ASSERT_, mrpt::math::CDijkstra< TYPE_EDGES >::m_source_node_ID, mrpt::math::CDijkstra< TYPE_EDGES >::previous, and mrpt::math::CDijkstra< TYPE_EDGES >::previous_arcs.


Member Data Documentation

template<typename TYPE_EDGES >
std::map<TNodeID,TDistance> mrpt::math::CDijkstra< TYPE_EDGES >::d [protected]

Definition at line 78 of file dijkstra.h.

Referenced by mrpt::math::CDijkstra< TYPE_EDGES >::CDijkstra().

template<typename TYPE_EDGES >
const TNodeID mrpt::math::CDijkstra< TYPE_EDGES >::INVALID_TNODEID = static_cast<TNodeID>(-1) [static]

Definition at line 57 of file dijkstra.h.

template<typename TYPE_EDGES >
TNodeID mrpt::math::CDijkstra< TYPE_EDGES >::m_source_node_ID [protected]

Definition at line 82 of file dijkstra.h.

Referenced by mrpt::math::CDijkstra< TYPE_EDGES >::getShortestPathTo().

template<typename TYPE_EDGES >
std::map<TNodeID,TPrevious> mrpt::math::CDijkstra< TYPE_EDGES >::previous [protected]

template<typename TYPE_EDGES >
std::map<TNodeID, std::pair<TNodeID,TNodeID> > mrpt::math::CDijkstra< TYPE_EDGES >::previous_arcs [protected]

template<typename TYPE_EDGES >
std::map<TNodeID, bool> mrpt::math::CDijkstra< TYPE_EDGES >::visited [protected]

Definition at line 81 of file dijkstra.h.

Referenced by mrpt::math::CDijkstra< TYPE_EDGES >::CDijkstra().




Page generated by Doxygen 1.5.9 for MRPT 0.7.1 SVN: at Mon Aug 17 22:32:05 EDT 2009