我的路径查找方法接收两个包含id、名称、x/y坐标以及存储在数组列表中的路径的对象。路径数据是它可以直接连接到的每个对象的id。目标是递归调用我的方法，直到找到使用最短距离的目标，当到达终点时返回true。

问题是：如果从你来的节点的距离比当前节点路径中其他节点的距离短，那么它将导致两个节点之间来回弹跳的无限循环。我已经为这个问题挣扎了几个小时，可能是想得太复杂了。任何建议或意见将不胜感激！

算法如下：

while (!pathfound) {    current = findPath(current, end);}public static Place findPath(Place curPlace, Place endPlace) {    ArrayList<Integer> path = curPlace.path;    int id;    double lastdist = 999;    double distance;    Place bestPlace = null;    for (int i = 0; i < path.size(); i++) {        id = curPlace.path.get(i);        distance = distance(getPlace(id), curPlace)                + distance(getPlace(id), endPlace);        if (distance < lastdist) {            bestPlace = getPlace(id);        }         lastdist = distance;    }    if (result.length() == 0) {        result += bestPlace.name;    } else {        result += ", " + bestPlace.name;    }    System.out.println("CURCITY: " + bestPlace.id);    System.out.println(result);    System.out.println(lastdist);    if (bestPlace == endPlace) {        pathfound = true;    }    return bestPlace;}

你可以忽略result，它是用来跟踪经过的节点的。如果你需要了解其他细节，请问我。

回答：

如果可以修改Place，你可以添加一个布尔类型的“已访问”标志。在运行算法之前将所有标志重置为false；访问时设置为true，离开时设置为false（别忘了在递归退出时取消设置它们 – 如果你正确地这样做，你甚至可以避免在开始前显式重置标志）。跳过标志为true的节点。

一个更短视的选项是将最后访问的Place作为参数传递给函数，并跳过那个节点。这不会防止更大的循环，但可能完全适合你的情况，并且是最简单的实现方式。

以上两种方法都是O(1)且开销最小。如果你不能修改Place，你可以存储一个已访问地点的Set（在递归退出时从集合中移除它们），并跳过已经在该集合中的地点。根据你的性能要求，如果你使用HashSet，你将需要想出一个合适的哈希函数。

沿着这个思路，如果你的ID号是唯一的并且覆盖一个合理大小的有限范围，以ID号为索引的boolean[]在这里是集合的一个常数时间的替代方案（它本质上是“已访问”标志选项，但标志存储在外部）。