ブーストダイクストラ最短パス - どのように距離だけでなく最短パスを得ることができますか？

Question

Boostライブラリを使用して、あるポイントから別のポイントへの最短経路を取得する必要があります。私はサンプルコードを見てきました。ただし、この例では全体の距離を取得する方法のみを示しています。私はどのくらい先のマップを実際に反復するかを理解しようとしています最短パスを取得し、私はそれを把握することはできません。私は、件名にこれら二つの質問を読んだ：

Dijkstra Shortest Path with VertexList = ListS in boost graph

Boost:: Dijkstra Shortest Path, how to get vertice index from path iterator?

をしかし提供の両方の例では、IndexMapのtypedefが率直に言って、Visual Studioのコンパイラで動作するように見えるとしませんBoostのtypedefは私にとってはちょっと混乱しています。ここの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

このわずかに中間セグメントはセグメント距離とともに他のノードに行くから表示するように変更llonesmiz's codeある：

OUTPUT

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] 

CODE

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