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 に答える