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));
}

Answer 2

Replace each vertex by a vertex pair linked with a link weight equal to the original vertex weight.

Like this:

Notes:

• If your graph is undirected, then the new link between each pair of nodes must be undirected. For a directed graph, you will need two new links between each node pair, one going in each direction and both weighted as the original vertex.

• Name the new nodes as new1-originalnodename and new2-originalnodename In the calculated path remove the hops between the new nodes and restore the original node.

• For the start and end nodes you can choose either of the new node pairs generated for these nodes as start and end.