Boost dijkstra shortest_path — как получить кратчайший путь, а не только расстояние?

Question

Мне нужно использовать библиотеку Boost, чтобы получить кратчайший путь из одной точки в другую.Я просмотрел пример кода, и за ним довольно легко следовать.Однако в примере показано только, как получить общие расстояния.Я пытаюсь понять, как перебрать карту-предшественницу, чтобы на самом деле получать кратчайший путь, и я не могу его понять.Я прочитал эти два вопроса по этой теме:

Кратчайший путь Дейкстры с VertexList = ListS в графе повышения

Способствовать росту::Кратчайший путь Дейкстры, как получить индекс вершины из итератора пути?

Но в обоих приведенных примерах определение типа IndexMap, похоже, не работает с компилятором Visual Studio, и, честно говоря, определения типа Boost меня немного сбивают с толку, и мне трудно во всем этом разобраться.Основываясь на приведенном здесь примере кода Boost, может ли кто-нибудь сказать мне, как я могу просто получить из него путь?Я был бы очень благодарен.

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

Answer 1

Если вы просто хотите получить путь от карты предшественника, вы можете сделать это так.

//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;

.

Answer 2

Это код Илонесмиза слегка изменен для отображения промежуточных сегментов, идущих от 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;
}