बूस्ट dijkstra shortest_path - आप सबसे छोटा रास्ता कैसे प्राप्त कर सकते हैं न केवल दूरी?

Question

मुझे बूस्ट लाइब्रेरी का उपयोग करने के लिए एक बिंदु से दूसरे बिंदु तक सबसे छोटा रास्ता प्राप्त करने की आवश्यकता है। मैंने उदाहरण कोड को देखा है और यह पालन करना आसान है। हालांकि, उदाहरण केवल दिखाता है कि समग्र दूरी कैसे प्राप्त करें। मैं वास्तव में को प्राप्त करने के लिए पूर्ववर्ती मानचित्र पर पुन: प्रयास करने का तरीका जानने का प्रयास कर रहा हूं और मुझे यह पता लगाना प्रतीत नहीं होता है। मैं इस विषय पर इन दो सवालों पढ़ा है:

Dijkstra Shortest Path with VertexList = ListS in boost graph

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

लेकिन उदाहरण प्रदान की दोनों में, IndexMap typedef दृश्य स्टूडियो संकलक और, स्पष्ट रूप से साथ काम नहीं लगता है , Typedefs बूस्ट मुझे थोड़ा उलझन में हैं और मुझे यह सब कुछ पता लगाने में परेशानी हो रही है। यहां बूस्ट उदाहरण कोड के आधार पर, क्या कोई मुझे बता सकता है कि मैं इसे कैसे निकाल सकता हूं? मैं बहुत आभारी रहूंगा।

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 थोड़ा मध्यवर्ती क्षेत्रों खंड दूरी के साथ-साथ अन्य नोड के लिए एक से जा रहा प्रदर्शित करने के लिए संशोधित है:

आउटपुट

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