template class mrpt::graphs::CDijkstra

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

The constructor takes as input the graph (a set of directed edges) and computes the spanning tree. Successive calls to CDijkstra::getShortestPathTo() then return the paths efficiently using that cached tree.

The entire spanning tree can be also retrieved via CDijkstra::getTreeGraph().

Input graphs are represented by instances of (or classes derived from) mrpt::graphs::CDirectedGraph, with nodes indexed by numerical values of type mrpt::graphs::TNodeID.

The second template argument MAPS_IMPLEMENTATION allows choosing between:

See a complete C++ code example.

#include <mrpt/graphs/dijkstra.h>

template <
    class TYPE_GRAPH,
    class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_stdmap
    >
class CDijkstra
{
public:
    // typedefs

    typedef TYPE_GRAPH graph_t;
    typedef typename graph_t::edge_t edge_t;
    typedef std::list<TPairNodeIDs> edge_list_t;
    typedef std::function<double(const graph_t&graph, TNodeID const id_from, TNodeID const id_to, const edge_t&edge)> functor_edge_weight_t;
    typedef std::function<void(const graph_t&graph, size_t visitedCount)> functor_on_progress_t;
    typedef CDirectedTree<const edge_t*> tree_graph_t;

    // structs

    struct TDistance;
    struct TPrevious;

    // construction

    CDijkstra(
        const graph_t& graph,
        const TNodeID source_node_ID,
        functor_edge_weight_t functor_edge_weight = functor_edge_weight_t(),
        functor_on_progress_t functor_on_progress = functor_on_progress_t(),
        const size_t maximum_distance = std::numeric_limits<size_t>::max()
        );

    //
methods

    std::optional<double> getNodeDistanceToRoot(TNodeID const id) const;
    const std::set<TNodeID>& getListOfAllNodes() const;
    TNodeID getRootNodeID() const;
    const list_all_neighbors_t& getCachedAdjacencyMatrix() const;
    void getShortestPathTo(TNodeID const target_node_ID, edge_list_t& out_path) const;
    edge_list_t getShortestPathTo(TNodeID const target_node_ID) const;
    void getTreeGraph(tree_graph_t& out_tree) const;
    tree_graph_t getTreeGraph() const;
};

Typedefs

typedef TYPE_GRAPH graph_t

The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class.

typedef typename graph_t::edge_t edge_t

The type of edge data in graph_t.

typedef std::list<TPairNodeIDs> edge_list_t

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

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)

Construction

CDijkstra(
    const graph_t& graph,
    const TNodeID source_node_ID,
    functor_edge_weight_t functor_edge_weight = functor_edge_weight_t(),
    functor_on_progress_t functor_on_progress = functor_on_progress_t(),
    const size_t maximum_distance = std::numeric_limits<size_t>::max()
    )

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.

An optional maximum distance (topological hop counts, or per functor_edge_weight if provided) to build the tree up to some limit. Use it if you are not interested in the entire tree.

maximum_distance was added in MRPT 2.4.1

Parameters:

std::exception

If the source nodeID is not found in the graph

See also:

getShortestPathTo(), getTreeGraph()

Methods

std::optional<double> getNodeDistanceToRoot(TNodeID const id) const

Return the distance from the root node to any other node using the Dijkstra-generated tree, or std::nullopt if the node ID is unknown or if it was farther away from root than the maximum topological distance passed in the constructor.

const std::set<TNodeID>& getListOfAllNodes() const

Return the set of all known node IDs (actually, a const ref to the internal set object).

TNodeID getRootNodeID() const

Return the node ID of the tree root, as passed in the constructor.

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.

See also:

mrpt::graphs::CDirectedGraph::getAdjacencyMatrix

void getShortestPathTo(TNodeID const 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.

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.

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

Parameters:

std::exception

If the given node was out of the maximum topological search radius passed to the constructor.

See also:

getTreeGraph

edge_list_t getShortestPathTo(TNodeID const target_node_ID) const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

(new in MRPT 2.4.1)

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.

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.

See also:

getShortestPathTo