Call boosts dijkstra shortest paths algorithm using a external weight map-CodePudding

I want to create a graph and call Dijkstra multiple times using different weight maps. I read that I can use an associative_property_map to map edges to weights but I don't know how to call Dijkstra using this custom map as a weight map.

#include <iostream>
#include <vector>
#include <map>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>


typedef boost::adjacency_list<boost::vecS, 
                              boost::vecS, 
                              boost::undirectedS>
                                                                graph;
typedef boost::graph_traits<graph>::edge_descriptor             edge_desc;
typedef boost::graph_traits<graph>::vertex_descriptor          vertex_desc;
typedef std::map<edge_desc, boost::edge_weight_t>               edge_weight_map;                 
typedef boost::associative_property_map<edge_weight_map>        weight_map; 

void dijkstra_path(const graph &G, const weight_map &w_map, int s, int t, std::vector<vertex_desc> &pred_map) {
  int n = boost::num_vertices(G);
  std::vector<int>         dist_map(n);
  
  boost::dijkstra_shortest_paths(G, s,
    boost::distance_map(
      boost::make_iterator_property_map(dist_map.begin(), boost::get(boost::vertex_index, G)))
      .predecessor_map(boost::make_iterator_property_map(pred_map.begin(), boost::get(boost::vertex_index, G))),
      w_map);

}

This is how I imagined it to work, can anybody tell me how to actually do this?

CodePudding user response：

You are mixing positional parameters with named parameters. The overload with named parameters doesn't take a weightmap positional: https://www.boost.org/doc/libs/1_80_0/libs/graph/doc/dijkstra_shortest_paths.html

So, add the weight map to the name parameters:

using graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using edge_desc       = boost::graph_traits<graph>::edge_descriptor;
using vertex_desc     = boost::graph_traits<graph>::vertex_descriptor;
using edge_weight_map = std::map<edge_desc, boost::edge_weight_t>;
using weight_map      = boost::associative_property_map<edge_weight_map>;

void dijkstra_path(const graph& G, weight_map w_map, int s, int /*t*/,
                   std::vector<vertex_desc>& pred_map) //
{
    int              n = boost::num_vertices(G);
    std::vector<int> dist_map(n);

    auto id = get(boost::vertex_index, G);
    auto dm = make_iterator_property_map(dist_map.begin(), id);
    auto pm = make_iterator_property_map(pred_map.begin(), id);

    boost::dijkstra_shortest_paths( //
        G, s,                       //
        boost::distance_map(dm)     //
            .predecessor_map(pm)    //
            .weight_map(w_map));
}

As a general tip, pass property maps by value. They're lightweight "reference" types designed to be very cheap to copy.