3

我想知道，我怎样才能在这样的图表中使用贝尔曼福特算法：

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

提前致谢。

4

1 回答 1

3

对于您的图形示例，在阅读您的图形并将源顶点设置为之后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_params有点令人困惑）。

于 2013-09-16T13:37:16.200 回答