小编Emm*_*Jay的帖子

我有一个增强图,每个边都有多个权重(想象一天中每小时一组权重).这些权重值中的每一个都存储在propretyEdge类中:

class propretyEdge {
    std::map<std::string,double> weights; // Date indexed 
}

我创建了一个包含这些属性的图形,然后用正确的值填充它.现在的问题是我想在图上的特定权重集上启动Dijkstra算法:例如,一个函数可能是:

void Dijkstra (string date, parameters ... )

那将使用

weights[date]

图的每个边的值.

我一遍又一遍地阅读文档,我无法清楚地知道自己要做什么.我当然需要写这样的东西,但我不知道要开始:

boost::dijkstra_shortest_paths (
    (*graph_m), 
    vertex_origin_num_l,
    // weight_map (get (edge_weight, (*graph_m)))
    // predecessor_map(boost::make_iterator_property_map(predecessors.begin(), get(boost::vertex_index, (*graph_m)))).
    // distance_map(boost::make_iterator_property_map(distances.begin (), get(vertex_index,(*graph_m) )))
    predecessor_map(predecessorMap).
    distance_map(distanceMap)
);

谢谢您的帮助.

编辑

感谢Sehe精彩的回答,我能够在MacOS和Ubuntu上做到我想要的.

但是当我们尝试在Visual Studio 2012上编译这段代码时,似乎VS并不是很擅长理解boost的指针功能.所以我们修改了Sehe的部分:

auto dated_weight_f = [&](Graph::edge_descriptor ed) {
    return g[ed].weights.at(date);
};

auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);

通过:

class dated_weight_f {
public:
  dated_weight_f(Graph* graph_p,std::string date_p){
    graph_m=graph_p;
    date_m=date_p;
  }
  typedef double …

我正在使用boost :: graph及其Dijkstra实现.

当有人使用Dijkstra算法时,可能知道图中2个节点之间的最短路径.但是,当您需要检查图中的所有节点以找到最短路径时,通常(如增强算法)Dijkstra会返回一个原点与图形的所有其他节点之间的所有距离.

当您只想要2个节点之间的路径时,该算法的一个简单改进是在算法到达目标节点时停止它.然后,您确定您对此最终目标节点的距离是最短的.

如何告诉boost Dijkstra算法在到达特定节点时停止？