c++ - 以 XY 坐标给出的点之间的最短路径距离

Question

我目前正在研究一个包含大约 800 个点的 X 和 Y 坐标的向量的项目。这些点代表了一个电力网络。我的目标是计算 A 点和 B 点之间的最短距离路径，该路径可以或不能沿着包含电线 XY 坐标的向量给出的路径定位。

我已经阅读了有关 Dijkstra 算法的信息，但由于我对它不太熟悉，我不确定我是否应该朝那个方向发展。如果我能从您那里得到任何可以指导我解决此问题的反馈或意见，我将非常感激。

Answer 1

Any pathfinding algorithm depends on paths, points are just meaningless. What you have now is a list of "waypoints". However you have not explained how those points connect. For example if any and every point is connected to each other point the shortest distance would simply be the pythagoral distance between A & B. - I'm also unsure what you mean by X-Y coordinates of electric lines, such a "line" would always have a start & end position?

So the first step is to add to each point not only the x,y coordinates, but also a list of connectable points.

Once you did this you can start using a pathfinding algorithm (In this case A* would seem better than Dijkstra's though). It would simply be a standard implementation with each "cost" the actual distance between a point. (And for A* the heuristic would be the pythagoral distance to the end point).

For a good tutorial about A* (and other algorithms) you should check Amit's pages

EDIT, in reply to the comments.

It seems the first step is to convert a set of line segments to "points". The way I would go through this is:

collection AllPoints {containing Location & LinksToOtherPoints}
for each Segment
    get start/end Point of Segment
    if Point.Location is not in allPoints
        add Point to AllPoints
    add the other Point of Segment to LinksToOtherPoints

You then have simply a list with all points & the connections between them. As you have to constantly search the allPoints collection I suggest storing that in a binary tree structure (sets?).

Answer 2

对于计算最短路径 Dijakstra 会很好。

使用A*可以获得更快的结果，它使用距离的最佳猜测，以便将搜索集中在正确的方向上，从而更快地到达那里。

如果您重复查询相同的数据集，那么记忆化就可以了。

那些推荐蛮力算法的人是傻瓜——花一点时间来学习如何编写一个有效的解决方案是值得的。但是您可以使用Floyd-Warshall 算法计算所有点之间的最短路径。不幸的是，这不会告诉你最短路径有多长。

Answer 3

只需计算所有可能路径的距离并选择最短的路径。800 条路径对于现代 PC 来说不算什么。你甚至不会注意到它。