java - 从集合中找到二维点之间的最短路径

Question

我的场景中有一个二维点列表，并且这些点之间的连接数组存储为无序对

Pair 的定义与此处完全相同，如何在 Java 中为无序对编写一个集合

所以我有 ：

ArrayList<PointF> mPoints = new ArrayList<PointF>();

ArrayList<Pair<PointF>> mConnections = new ArrayList<Pair<PointF>>();

//
PointF mStartPoint = mPoints.get(0);
PointF mEndPoint = mPoints.get(80);

我需要找到将我从源点引导到目标点的点数组。

我想为每对添加有关距离的信息，但接下来呢？

Answer 1

这是标准路径查找问题的一个实例。

如果您需要有保证的精确解决方案，请使用Dijkstra's algorithm 之类的方法。如果您需要更高效的方法，但在某些情况下可以接受次优解决方案，请使用A* 算法。

Answer 2

有关解决方案，请参阅http://en.wikipedia.org/wiki/Dijkstras_algorithm#Algorithm。