그래프에서 두 vertives 간의 최단 경로를 찾는 방법은 무엇입니까?

Question

나는 게임을위한 GPS 시스템을 만들고 있는데, 길에서 두 지점 사이의 최단 경로를 선택할 수 있습니다.

#include <boost/graph/graph_traits.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/dijkstra_shortest_paths.hpp> 

using namespace boost; 
using namespace std; 

class GPS 
{ 
public: 
    typedef   boost::property<boost::edge_weight_t, float>      Distance; 
    typedef   adjacency_list<vecS, vecS, directedS, boost::no_property, Distance> Graph; 
    typedef   int                 Node; 
    typedef   std::pair<int, int>             Edge; 
    typedef   property_map<Graph, edge_weight_t>::type       weightmap_t;     
    typedef   graph_traits <Graph>::vertex_descriptor       vertex_descriptor; 
    typedef   graph_traits <Graph>::edge_descriptor        edge_descriptor; 
private: 
    vector<Edge>       Edges; 
    Graph         Nodes; 
public: 
    GPS() 
    { 

    } 
    ~GPS() 
    { 

    } 
    //returns amount of edges added: 0, 1 or 2 
    char AddEdge(Node from, Node to, Distance weight = 0.0f, bool BothDirections = false) 
    { 
     char added = 0; 
     if(add_edge(from,to,weight,Nodes).second) 
      ++added; 
     if(BothDirections) 
     { 
      if(add_edge(to,from,weight,Nodes).second) 
       ++added; 
     } 
     return added; 
    } 
    //returns the added node, 
    //specify your own vertex identificator if wanted 
    //(for maintaining backwards compatibility with old graphs saved in gps.dat files) 
    Node AddNode(int id = -1) 
    { 
     if(id == -1) 
      return add_vertex(Nodes); 
     else 
      return vertex(id,Nodes); 
    } 
    //get the shortest path between 'from' and 'to' by adding all nodes which are traversed into &path 
    void Path(Node from, Node to, vector<Node> &path) 
    { 
     std::vector<vertex_descriptor> p(num_vertices(Nodes)); 
     std::vector<int> d(num_vertices(Nodes)); 
     weightmap_t weightmap = get(edge_weight, Nodes); 
     vertex_descriptor s = vertex(from, Nodes); 
     dijkstra_shortest_paths(Nodes, s, predecessor_map(&p[0]).distance_map(&d[0])); 

     //what here? and are there faster algorithms in boost graph than dijkstra (except A*)? 
    } 
}; 

가 지금은 두 꼭지점 사이의 경로를 찾는이 오면 정말 끼 었어 : 나는 다음과 같이 보이는 클래스를 만들어 동해 지금으로

.

나는 익스트라의 documentation 및 example을 보았다하지만 난 그냥 이해가 안가 ..

다른 알고리즘이 설정에 힘들어 보인다.

어떻게 최단 경로를 찾을 수 있습니까? 모든 매개 변수와 함수 및 내용은 매우 혼란 스럽습니다. "내 집에서 요리하고 느린"라이브러리에서 벗어나고 싶습니다.

Answer 1

이 코드는 각 노드에 대해 (부스트의 예제 코드에서 가져온)

std::cout << "distances and parents:" << std::endl; 
    graph_traits <graph_t>::vertex_iterator vi, vend; 
    for (boost::tie(vi, vend) = vertices(g); vi != vend; ++vi) { 
     std::cout << "distance(" << *vi << ") = " << d[*vi] << ", "; 
     std::cout << "parent(" << *vi << ") = " << p[*vi] << std:: 
     endl; 
    } 

그래서 당신이해야 할 모든

n= dest; 
while (n!=src) { 
path.push_back(n); 
n = p[n]; // you're one step closer to the source.. 
}