c++ - 使用 Boost Graph Library 和 Bellman-Ford 算法

Question

我想知道，我怎样才能对这样的图使用 bellman-ford 算法:

typedef boost::property <boost::vertex_name_t,std::string> VertexProperty;
typedef boost::property <boost::edge_weight_t,int> EdgeProperty;
typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::directedS,VertexProperty,EdgeProperty> DiGraph;

通过这种方式获得:

boost::dynamic_properties dp;
dp.property("name",boost::get(boost::vertex_name,digraph));
dp.property("weight",boost::get(boost::edge_weight,digraph));
try
{
  read_graphml(file_stream,digraph,dp);
}
catch(boost::graph_exception &ge)
{
  myprint<<ge.what();
}

提前致谢。

Answer 1

对于您的图表示例，在阅读您的图表并在 source_node_index 中设置您的源顶点之后:

const int nb_vertices = num_vertices(g);

// gets the weight property
property_map<DiGraph, boost::edge_weight_t>::type weight_pmap = 
  get(boost::edge_weight_t(), g);

// init the distance
std::vector<int> distance(nb_vertices, (std::numeric_limits<int>::max)());
distance[source_node_index] = 0; // the source is at distance 0

// init the predecessors (identity function)
std::vector<std::size_t> parent(nb_vertices);
for (int i = 0; i < nb_vertices; ++i)
  parent[i] = i;

// call to the algorithm
bool r = bellman_ford_shortest_paths(
  g, 
  nb_vertices, 
  weight_map(weight_pmap).
    distance_map(&distance[0]).
      predecessor_map(&parent[0])
  );

对 bellman_ford_shortest_paths 的调用有点奇怪而且没有很好的记录(这个 bgl_named_pa​​rams 有点令人困惑)。