Search code examples
c++boostgraphshortest-path

Finding the shortest path in a boost graph using Dijkstra


I am new to the boost graph library and I am trying to find the shortest path from one vertex to another one in the Graph using the boost graph library. I found some instructions on how to use the predecessor map in order to do that but it won't work for me. When I try to call p[some_vertex] I get an error saying the [] operator is not defined. Can someone tell me why and what I am doing wrong?

typedef property<edge_weight_t, double, property<edge_index_t, tElementIDVector>> tEdgeProperty;
typedef property<vertex_index_t, tElementID> VertexIDPorperty;
typedef adjacency_list<vecS, setS, directedS, VertexIDPorperty, tEdgeProperty> tGraph;

typedef tGraph::vertex_descriptor tVertex;
typedef tGraph::edge_descriptor tEdge;

vector<tVertex> p(num_vertices(graph));
vector<double> d(num_vertices(graph));
// call dijkstra algorithm from boost to find shortest path
dijkstra_shortest_paths(graph, s,
    predecessor_map(&p[0]).
    distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));

//find path from start to end vertex
list<tVertex> pathVertices;
tVertex current = goal;
while (current != start)
{
    pathVertices.push_front(current);
    current = p[current];     //this is where the error occures
}

Solution

  • I couldn't get your idea to work and had to make some other changes now, too which is why i changed my predecessor map now to:

    typedef boost::property_map < tGraph, boost::vertex_index_t >::type IndexMap;
    typedef boost::iterator_property_map < tVertex*, IndexMap, tVertex, tVertex& > PredecessorMap;
    tVertex s = start;
    IndexMap indexMap = get(vertex_index, graph);
    vector<tVertex> p(num_vertices(graph));
    PredecessorMap predecessorMap(&p[0], indexMap);
    vector<double> d(num_vertices(graph));
    
    // call dijkstra algorithm from boost to find shortest path
    dijkstra_shortest_paths(graph, s, predecessor_map(predecessorMap).distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));
    //find path from start to end vertex
    list<tVertex> pathVertices;
    tVertex current = goal;
    while (current != start)
    {
        pathVertices.push_front(current);
        current = predecessorMap[current];
    }
    

    and this actually works now :)