Нахождение кратчайшего пути в буст-графе с помощью Дейкстры - PullRequest
Новая
       24

Нахождение кратчайшего пути в буст-графе с помощью Дейкстры

0 голосов
/ 15 мая 2018

Я новичок в библиотеке графов надстроек и пытаюсь найти кратчайший путь от одной вершины к другой в графе, используя библиотеку надстрочных графов.Я нашел несколько инструкций о том, как использовать карту предшественника, чтобы сделать это, но она не будет работать для меня.Когда я пытаюсь вызвать p [some_vertex], я получаю сообщение о том, что оператор [] не определен.Может кто-нибудь сказать мне, почему и что я делаю не так? 

typedef property<edge_weight_t, double, property<edge_index_t, tElementIDVector>> tEdgeProperty;
typedef property<vertex_index_t, tElementID> VertexIDPorperty;
typedef adjacency_list<vecS, setS, directedS, VertexIDPorperty, tEdgeProperty> tGraph;

typedef tGraph::vertex_descriptor tVertex;
typedef tGraph::edge_descriptor tEdge;

vector<tVertex> p(num_vertices(graph));
vector<double> d(num_vertices(graph));
// call dijkstra algorithm from boost to find shortest path
dijkstra_shortest_paths(graph, s,
    predecessor_map(&p[0]).
    distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));

//find path from start to end vertex
list<tVertex> pathVertices;
tVertex current = goal;
while (current != start)
{
    pathVertices.push_front(current);
    current = p[current];     //this is where the error occures
}

Ответы [ 2 ]

0 голосов
/ 16 мая 2018

Я не смог воплотить вашу идею в жизнь, и теперь мне пришлось внести некоторые другие изменения, поэтому я изменил свою карту предшественника сейчас: 

typedef boost::property_map < tGraph, boost::vertex_index_t >::type IndexMap;
typedef boost::iterator_property_map < tVertex*, IndexMap, tVertex, tVertex& > PredecessorMap;
tVertex s = start;
IndexMap indexMap = get(vertex_index, graph);
vector<tVertex> p(num_vertices(graph));
PredecessorMap predecessorMap(&p[0], indexMap);
vector<double> d(num_vertices(graph));

// call dijkstra algorithm from boost to find shortest path
dijkstra_shortest_paths(graph, s, predecessor_map(predecessorMap).distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, graph))));
//find path from start to end vertex
list<tVertex> pathVertices;
tVertex current = goal;
while (current != start)
{
    pathVertices.push_front(current);
    current = predecessorMap[current];
}

и теперь это действительно работает:)

0 голосов
/ 15 мая 2018

От cppreference :

станд :: вектор :: оператор [] 

reference       operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;

принимает size_t с указанием положения элемента вектора.

Однако в вашем коде current имеет тип tVertex.

Если вы хотите использовать operator[] с параметром tVertex, вы должны переопределить его.

...