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

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*)?
}
};

Теперь я действительно застрял, когда дело доходит до поиска пути между двумя вершинами.

Я посмотрел вверх документация а также пример для Дейкстры, но я просто не понимаю ..

Любые другие алгоритмы кажутся сложнее в настройке.

Как мне найти кратчайший путь? Все параметры, функции и прочее очень сбивают с толку .. Я хочу переключиться на повышение, отойти от «моих собственных и медленных» библиотек.

0

boost-graph c++shortest-path

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Этот фрагмент кода даст вам, для каждого узла, какой узел вы должны пройти, чтобы достичь источника, следуя кратчайшему пути: (взят из примера кода в 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..
}

0