how to calculate the shortest path with ”vertex weights“ using boost::dijkstra_shortest_paths?

Question

I'm trying to calculate the shortest path on a graph with vertex weights and edge weights, but boost::dijkstra_shortest_paths doesn't calculate the weights passing through the vertices.

I tried customizing weight_map, but it always reported an error when running. The following is my code

    auto custom_weight_map = [&g](const Graph::edge_descriptor& e) -> float {
        float vertex_weight = g[target(e, g)].weight;
        float edge_weight = get(boost::edge_weight, g, e);
        return vertex_weight + edge_weight;
    };

    boost::dijkstra_shortest_paths(
        g, source_vertex,
        boost::predecessor_map(
            boost::make_iterator_property_map(
                predecessors.begin(), boost::get(boost::vertex_index, g)))
            .distance_map(boost::make_iterator_property_map(
                distances.begin(), boost::get(boost::vertex_index, g)))
            .weight_map(custom_weight_map));

Answer 1

The custom weight map needs to be a property map: doc

The type WeightMap must be a model of Readable Property Map. The edge descriptor type of the graph needs to be usable as the key type for the weight map. The value type for this map must be the same as the value type of the distance map.

The simplest way I think to do it is to use a function property map or perhaps transform property map:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/function_property_map.hpp>

struct VertexProps { double weight; };
using Graph = boost::adjacency_list< //
    boost::vecS, boost::vecS, boost::directedS, VertexProps, boost::property<boost::edge_weight_t, double>>;
using V = Graph::vertex_descriptor;
using E = Graph::edge_descriptor;

int main() {
    Graph g(10);
    auto  vidx          = get(boost::vertex_index, g);
    auto  vertex_weight = get(&VertexProps::weight, g);
    auto  edge_weight   = get(boost::edge_weight, g);

    for (V v : boost::make_iterator_range(vertices(g)))
        vertex_weight[v] = static_cast<double>(v) * 100;

    auto source_vertex = vertex(0, g);
    std::vector<V>      predecessors(num_vertices(g));
    std::vector<double> distances(num_vertices(g), INFINITY);

    auto sum_weights = boost::make_function_property_map<E>(
        [=, &g](E e) { return vertex_weight[source(e, g)] + edge_weight[e]; });

    dijkstra_shortest_paths(g, source_vertex,
                            predecessor_map(make_iterator_property_map(predecessors.begin(), vidx))
                                .distance_map(make_iterator_property_map(distances.begin(), vidx))
                                .weight_map(sum_weights));
}