我要爲偷懶的方法,只是給一些代碼,演示瞭如何做到這一點:)
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>
struct Edge {
Edge(float weight_) : weight(weight_) {}
float weight;
};
// simple function
float combine(float a, float b){
return std::max(a, b);
}
// functor
struct Combine{
// Some internal state
float operator()(float a, float b) const {
return std::max(a, b);
}
};
int main(int, char**){
typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS, boost::no_property, Edge > graph_t;
typedef boost::graph_traits <graph_t>::vertex_descriptor vertex_t;
graph_t g;
vertex_t a = boost::add_vertex(g);
vertex_t b = boost::add_vertex(g);
vertex_t c = boost::add_vertex(g);
vertex_t d = boost::add_vertex(g);
boost::add_edge(a, b, Edge(3), g);
boost::add_edge(b, c, Edge(3), g);
boost::add_edge(a, d, Edge(1), g);
boost::add_edge(d, c, Edge(4), g);
std::vector<vertex_t> preds(4);
// Traditional dijsktra (sum)
boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::weight,g)));
assert(preds[c] == d);
assert(preds[d] == a);
// Dijkstra with custom combine as a function
boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::weight,g)).distance_combine(&combine));
assert(preds[c] == b);
assert(preds[b] == a);
// Dijkstra with custom combine as a functior
boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::weight,g)).distance_combine(Combine()));
// Dijkstra with custom combine as a lambda
boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(boost::get(&Edge::weight,g)).distance_combine([](float a, float b){return std::max(a,b);}));
return 0;
}
事實上,它的工作有更多的摸索一點。我定義了 'template T comb(T&a,T&b){return std :: max(a,b); }',並在我的Dijkstra中通過梳理。謝謝! –
Balise