主页 / 问题 / 601140
Accepted
yrHeTateJlb
Asked:2020-12-08 21:19:08 +0000 UTC2020-12-08 21:19:08 +0000 UTC

将父子对转换为路由

  • 772

我需要在无向未加权图上找到从每个人到每个人的最短路径。经过一番谷歌搜索后，我发现了 Dijkstra 算法。该算法的输出类似于QMap<int, int>。第一个int是父节点，第二个是最短路径中的后继节点。

例如，如果您在这样的图中寻找从零开始的顶点路径：

图形

我会得到这个集合：
0 - 0
1 - 0
2 - 3
3 - 1
4 - 1

现在的问题是如何有效地将其转换为路径？

现在我这样做：

//Поиск родителя
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;
}

它可以工作，甚至可以正常工作。但我怀疑这是最有效的方法。我多次在地图中寻找相同的值。也许有可能以某种方式在一次通过QMap<int, int>中构建路由，或者在执行算法时立即构建路由？

一个最小的例子，如果突然有人需要它

c++

1 个回答

  1. Best Answer

    这里最有效的方法是从叶到根遍历树。为此，您首先需要将散列转换为数组。也就是会有这样一个p值的数组p[] = {0, 0, 3, 1, 1}。这非常方便，因为多次遍历数组非常快，条件i==p[i]意味着我们已经到达起点。

    此外，为了构建一条路径，比如说，到顶部x，您只需要沿着树走直到我们找到根。示例伪代码：

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

    该数组way将包含所需的向后路径。您需要为所有x需要找到路径的对象运行此循环。您的实施中的刹车主要是由于树的存储效率低下，而不是因为某些部分被多次通过。使用相同的方法，刹车不太可能。好吧，除非你有数万个顶点。

    另一个注意事项。Dijkstra 的算法在这里效率低下，它在加权图中搜索路径，在非加权图中搜索最短路径的一种更快的方法是广度优先搜索。如果你仍然想要 Dijkstra，那么优化路径的恢复是没有意义的，因为刹车将在 Dijkstra 中。

    • 6

相关问题