Boost dijkstra shortest_path — как вы можете получить кратчайший путь, а не только расстояние?
У меня есть необходимость использовать библиотеку Boost, чтобы получить кратчайший путь из одной точки в другую. Я просмотрел пример кода, и за ним довольно легко следовать. Тем не менее, пример показывает только, как получить общие расстояния. Я пытаюсь выяснить, как перебрать карту предшественника на самом деле получить кратчайший путь, и я не могу понять это. Я прочитал эти два вопроса на эту тему:
Кратчайший путь Дейкстры с VertexList = ListS в буст-графе
Boost :: Dijkstra Shortest Path, как получить индекс вершины из итератора пути?
Но в обоих приведенных примерах определение типа IndexMap, похоже, не работает с компилятором Visual Studio, и, честно говоря, определение типа Boost немного сбивает меня с толку, и у меня возникли некоторые проблемы, когда я все это выяснил. Основанный на примере кода Boost, кто-нибудь может сказать мне, как я могу просто найти путь из него? Я был бы очень благодарен.
http://www.boost.org/doc/libs/1_46_1/libs/graph/example/dijkstra-example.cpp
Решение
Если вы просто хотите получить путь от карты предшественника, вы можете сделать это следующим образом.
//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;
Другие решения
Это код Илонесмиза немного изменен для отображения промежуточных сегментов, идущих от 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;
}