The Dijkstra algorithm for finding the shortest path between a given source node in a (weighted) directed graph and all other nodes in the form of a tree.
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 efficiently from the root.
The entire generated tree can be also retrieved with getTreeGraph.
Input graphs are represented by instances of (or classes derived from) mrpt::graphs::CDirectedGraph, and node's IDs are uint64_t values, although the type mrpt::utils::TNodeID is also provided for clarity in the code.
The second template argument MAPS_IMPLEMENTATION allows choosing between a sparse std::map<> representation (using * mrpt::utils::map_traits_stdmap) for several intermediary and final results, and an alternative (using mrpt::utils::map_traits_map_as_vector as argument) dense implementation which is much faster, but can be only used if the TNodeID's start in 0 or a low value.
See <a href="http://www.mrpt.org/Example:Dijkstra_optimal_path_search_in_graphs"
this page for a complete example.
Definition at line 103 of file dijkstra.h.
#include <mrpt/graphs/dijkstra.h>
Classes | |
| struct | TDistance |
| Auxiliary struct for topological distances from root node. More... | |
| struct | TPrevious |
| Auxiliary struct for backward paths. More... | |
Public Types | |
Useful typedefs | |
| typedef TYPE_GRAPH | graph_t |
| The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class. More... | |
| typedef graph_t::edge_t | edge_t |
| The type of edge data in graph_t. More... | |
| typedef std::list< TPairNodeIDs > | edge_list_t |
| A list of edges used to describe a path on the graph. More... | |
Public Member Functions | |
| CDijkstra (const graph_t &graph, const TNodeID source_node_ID, double(*functor_edge_weight)(const graph_t &graph, const TNodeID id_from, const TNodeID id_to, const edge_t &edge)=NULL, void(*functor_on_progress)(const graph_t &graph, size_t visitedCount)=NULL) | |
| Constructor which takes the input graph and executes the entire Dijkstra algorithm from the given root node ID. More... | |
Protected Types | |
| typedef MAPS_IMPLEMENTATION::template map< TNodeID, std::set< TNodeID > > | list_all_neighbors_t |
| A std::map (or a similar container according to MAPS_IMPLEMENTATION) with all the neighbors of every node. More... | |
| typedef MAPS_IMPLEMENTATION::template map< TNodeID, TPairNodeIDs > | id2pairIDs_map_t |
| typedef MAPS_IMPLEMENTATION::template map< TNodeID, TDistance > | id2dist_map_t |
| typedef MAPS_IMPLEMENTATION::template map< TNodeID, TPrevious > | id2id_map_t |
Protected Attributes | |
| const TYPE_GRAPH & | m_cached_graph |
| const TNodeID | m_source_node_ID |
| id2dist_map_t | m_distances |
| All the distances. More... | |
| std::map< TNodeID, TDistance > | m_distances_non_visited |
| id2id_map_t | m_prev_node |
| id2pairIDs_map_t | m_prev_arc |
| std::set< TNodeID > | m_lstNode_IDs |
| list_all_neighbors_t | m_allNeighbors |
Query Dijkstra results | |
| typedef CDirectedTree< const edge_t * > | tree_graph_t |
| Type for graph returned by getTreeGraph: a graph like the original input graph, but with edge data being pointers to the original data (to save copy time & memory) More... | |
| double | getNodeDistanceToRoot (const TNodeID id) const |
| Return the distance from the root node to any other node using the Dijkstra-generated tree. More... | |
| const std::set< TNodeID > & | getListOfAllNodes () const |
| Return the set of all known node IDs (actually, a const ref to the internal set object). More... | |
| TNodeID | getRootNodeID () const |
| Return the node ID of the tree root, as passed in the constructor. More... | |
| const list_all_neighbors_t & | getCachedAdjacencyMatrix () const |
| Return the adjacency matrix of the input graph, which is cached at construction so if needed later just use this copy to avoid recomputing it. More... | |
| void | getShortestPathTo (const TNodeID target_node_ID, edge_list_t &out_path) const |
| Returns the shortest path between the source node passed in the constructor and the given target node. More... | |
| void | getTreeGraph (tree_graph_t &out_tree) const |
| Returns a tree representation of the graph, as determined by the Dijkstra shortest paths from the root node. More... | |
| typedef std::list<TPairNodeIDs> mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::edge_list_t |
A list of edges used to describe a path on the graph.
Definition at line 146 of file dijkstra.h.
| typedef graph_t::edge_t mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::edge_t |
The type of edge data in graph_t.
Definition at line 145 of file dijkstra.h.
| typedef TYPE_GRAPH mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::graph_t |
The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class.
Definition at line 144 of file dijkstra.h.
|
protected |
Definition at line 129 of file dijkstra.h.
|
protected |
Definition at line 130 of file dijkstra.h.
|
protected |
Definition at line 128 of file dijkstra.h.
|
protected |
A std::map (or a similar container according to MAPS_IMPLEMENTATION) with all the neighbors of every node.
Definition at line 127 of file dijkstra.h.
| typedef CDirectedTree<const edge_t *> mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::tree_graph_t |
Type for graph returned by getTreeGraph: a graph like the original input graph, but with edge data being pointers to the original data (to save copy time & memory)
Definition at line 398 of file dijkstra.h.
|
inline |
Constructor which takes the input graph and executes the entire Dijkstra algorithm from the given root node ID.
The graph is given by the set of directed edges, stored in a mrpt::graphs::CDirectedGraph class.
If a function functor_edge_weight is provided, it will be used to compute the weight of edges. Otherwise, all edges weight the unity.
After construction, call getShortestPathTo to get the shortest path to a node or getTreeGraph for the tree representation.
| std::exception | If the source nodeID is not found in the graph |
Definition at line 167 of file dijkstra.h.
References ASSERT_, mrpt::mrpt::format(), INVALID_NODEID, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_allNeighbors, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_distances, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_distances_non_visited, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_lstNode_IDs, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_arc, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_node, and THROW_EXCEPTION_FMT.
|
inline |
Return the adjacency matrix of the input graph, which is cached at construction so if needed later just use this copy to avoid recomputing it.
Definition at line 361 of file dijkstra.h.
References mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_allNeighbors.
|
inline |
Return the set of all known node IDs (actually, a const ref to the internal set object).
Definition at line 350 of file dijkstra.h.
References mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_lstNode_IDs.
|
inline |
Return the distance from the root node to any other node using the Dijkstra-generated tree.
| std::exception | On unknown node ID |
Definition at line 343 of file dijkstra.h.
References mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_distances, and THROW_EXCEPTION.
|
inline |
Return the node ID of the tree root, as passed in the constructor.
Definition at line 353 of file dijkstra.h.
References mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_source_node_ID.
|
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.
Definition at line 375 of file dijkstra.h.
References ASSERT_, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_arc, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_node, and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_source_node_ID.
|
inline |
Returns a tree representation of the graph, as determined by the Dijkstra shortest paths from the root node.
Note that the annotations on each edge in the tree are "const pointers" to the original graph edge data, so it's mandatory for the original input graph not to be deleted as long as this tree is used.
Definition at line 405 of file dijkstra.h.
References ASSERTMSG_, mrpt::graphs::CDirectedTree< TYPE_EDGES >::clear(), mrpt::graphs::CDirectedTree< TYPE_EDGES >::edges_to_children, mrpt::format(), mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_cached_graph, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_arc, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_source_node_ID, and mrpt::graphs::CDirectedTree< TYPE_EDGES >::root.
|
protected |
Definition at line 138 of file dijkstra.h.
Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getCachedAdjacencyMatrix().
|
protected |
Definition at line 123 of file dijkstra.h.
Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph().
|
protected |
All the distances.
Definition at line 133 of file dijkstra.h.
Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getNodeDistanceToRoot().
|
protected |
Definition at line 134 of file dijkstra.h.
Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra().
|
protected |
Definition at line 137 of file dijkstra.h.
Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getListOfAllNodes().
|
protected |
|
protected |
Definition at line 135 of file dijkstra.h.
Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getShortestPathTo().
|
protected |
| Page generated by Doxygen 1.8.14 for MRPT 1.5.7 Git: 5902e14cc Wed Apr 24 15:04:01 2019 +0200 at lun oct 28 01:39:17 CET 2019 | |