如何使用 boost::dijkstra_shortest_paths 计算具有“顶点权重”的最短路径？

Question

我正在尝试计算具有顶点权重和边权重的图上的最短路径，但是 boost::dijkstra_shortest_paths 不会计算通过顶点的权重。

我尝试自定义weight_map，但是运行时总是报错。以下是我的代码

    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

用链接权重等于原始顶点权重的顶点对替换每个顶点。

像这样：

Answer 2

自定义权重图需要是属性图：

WeightMap 类型必须是 Readable Property Map 的模型。图的边缘描述符类型需要可用作权重图的键类型。该地图的值类型必须与距离图的值类型相同。

我认为最简单的方法是使用 function property map 或者 transform property map:

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