11

あるポイントから別のポイントへの最短パスを取得するには、Boostライブラリを使用する必要があります。サンプルコードを確認しましたが、わかりやすくなっています。ただし、この例は、全体的な距離を取得する方法のみを示しています。先行マップを反復処理して実際に最短経路を取得する方法を理解しようとしていますが、理解できないようです。私はこの主題に関するこれらの2つの質問を読みました：

ブーストグラフのVertexList=ListSを使用したダイクストラ最短経路

Boost :: Dijkstra Shortest Path、パスイテレータから頂点インデックスを取得する方法は？

しかし、提供されている両方の例では、IndexMaptypedefはVisualStudioコンパイラでは機能しないようであり、率直に言って、Boost typedefは私には少し混乱しており、これらすべてを理解するのに問題があります。ここにあるBoostのサンプルコードに基づいて、パスを取得する方法を教えてもらえますか？とてもありがたいです。

http://www.boost.org/doc/libs/1_46_1/libs/graph/example/dijkstra-example.cpp

4

2 に答える 2

12

先行マップからパスを取得したいだけの場合は、次のように実行できます。

//p[] is the predecessor map obtained through dijkstra
//name[] is a vector with the names of the vertices
//start and goal are vertex descriptors
std::vector< graph_traits< graph_t >::vertex_descriptor > path;
graph_traits< graph_t >::vertex_descriptor current=goal;

while(current!=start) {
    path.push_back(current);
    current=p[current];
}
path.push_back(start);

//This prints the path reversed use reverse_iterator and rbegin/rend
std::vector< graph_traits< graph_t >::vertex_descriptor >::iterator it;
for (it=path.begin(); it != path.end(); ++it) {

    std::cout << name[*it] << " ";
}
std::cout << std::endl;
于 2012-10-01T15:36:59.957 に答える
3

これはllonesmiz のコードをわずかに変更して、A から他のノードに向かう中間セグメントをセグメント距離とともに表示するようにしています。

出力

A[0] C[1] D[3] E[1] B[1] 
A[0] C[1] 
A[0] C[1] D[3] 
A[0] C[1] D[3] E[1]

コード

// DISPLAY THE PATH TAKEN FROM A TO THE OTHER NODES

nodes  start = A;
for ( int goal=B; goal<=E; ++goal )
{
  std::vector< graph_traits< graph_t >::vertex_descriptor >  path;
  graph_traits< graph_t >::vertex_descriptor                 current=goal;

  while( current!=start )
  {
    path.push_back( current );
    current = p[current];
  }
  path.push_back( start );

  // rbegin/rend will display from A to the other nodes
  std::vector< graph_traits< graph_t >::vertex_descriptor >::reverse_iterator rit;
  int cum=0;
  for ( rit=path.rbegin(); rit!=path.rend(); ++rit) 
  {
    std::cout << name[*rit] << "[" << d[*rit]-cum << "] ";
    cum = d[*rit];
  }
  std::cout << std::endl;
}
于 2013-01-26T12:31:04.970 に答える