It took me to find on the undirected unweighted graph the shortest paths from all to all. A little googling stumbled upon Dijkstra's algorithm. At the output of this algorithm, I get something like QMap<int, int> . The first int is the parent, the second is the heir in the shortest path.

For example, if you look for paths to the vertices starting from zero in this graph:

Graph

I will get this set:
0 - 0
ten
2 - 3
3 - 1
4 - 1

Now the question is how to effectively transform it in a way?

Now I do it like this:

 //Поиск родителя QMap<int, int>::ConstIterator findParent(const QMap<int, int> &map, int child){ QMap<int, int>::ConstIterator parent = map.find(child); if(child == *parent){ return map.end(); } return parent; } //----------------------------------------------------------------------- //Построение маршрута QVector<int> route(const QMap<int, int> &map, int start){ QVector<int> route; route.append(start); forever{ QMap<int, int>::ConstIterator parent = findParent(map, route.last()); if(parent == map.end()){ break; } route.append(*parent); }; return route; } //----------------------------------------------------------------------- //Построение маршрутов QVector<QVector<int> > routes(const QMap<int, int> &map){ QVector<QVector<int> > routes; QMap<int, int>::ConstIterator begin = map.begin(); QMap<int, int>::ConstIterator end = map.end(); for(; begin != end; ++begin){ routes.append(route(map, begin.key())); } return routes; }

It works and even correctly. But I am tormented by doubts, this is the most effective way. Many times I look for the same values ​​in the map. Perhaps you can somehow build routes in a single pass through QMap<int, int> , or build routes right away when the algorithm runs?

Minimal example if suddenly someone needs

    1 answer 1

    The most effective way here is to walk through the tree from leaf to root. To do this, you must first convert your hash to an array. That is, there will be an array p with such values p[] = {0, 0, 3, 1, 1} . It is very convenient, since multiple passage through the array is very fast and the condition i==p[i] means that we have reached the starting point.

    Next, to build a path, say, to the vertex x , you just need to walk the tree until we find the root. Approximate pseudocode:

     x = желаемая_вершина; do { way[k++] = x; x = p[x]; } while (x!=p[x]);

    In the array of way will be the desired way back to front . You need to run this cycle for all x for which you need to find a path. The brakes you have in the implementation will be primarily due to the inefficient storage of wood, and not due to the fact that some areas pass several times. With the same approach, the brakes are unlikely. Well, unless you have tens of thousands of peaks.

    Another note. Dijkstra's algorithm is inefficient here, he is looking for a path in a weighted graph, a faster way to look for the shortest path in an unweighted graph is a search for width . If you want exactly Dijkstra, it makes no sense to optimize the restoration of the paths, because the brakes will be in Dijkstra.