Как найти кратчайший путь между двумя вершинами в графе?

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

Этот фрагмент кода даст вам, для каждого узла, какой узел вы должны следовать, чтобы достичь источника, следуя по кратчайшему пути: (взятый из примера кода в Boost)

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