无限递归java问题

Question

我正在尝试解决一个问题，但似乎无法解决这个问题。我尝试创建列表和集合来跟踪访问过的城镇，然后如果已经访问过则跳过，但到目前为止我的实现都没有起作用。

问题是，给定一个包含 AB5 等路线的图，它意味着从 A 镇到 B 的路线，距离为 5。现在给定输入 AB5、BC4、CD8、DC8、DE6、AD5、CE2、EB3、AE7 I我正在尝试找到从 B 到 B 的最短路径。答案应该是 9。

我发现问题的存在是因为递归检查了路径C到D，然后检查了所有D的路径。 D 包含一条到 C 的路线，然后它到达 C，这就是无限递归发生的地方。我如何实施检查以确保它不会无限循环 C 到 D 和 D 到 C 路线。

这是我针对此问题编写的函数：

public int shortestDistance(char startTown, char endTown, char currentTown, int distance, int step) {
        if (currentTown == endTown && step != 0) {
            return distance;
        }

        int shortestDistance = Integer.MAX_VALUE;
        for (char nextTown : graph.get(currentTown).keySet()) {
            shortestDistance = Math.min(shortestDistance, shortestDistance(startTown, endTown, nextTown,
                    distance + graph.get(currentTown).get(nextTown), step + 1));
        }
        return shortestDistance;
    }

Answer 1

这可能是 Dijkstra 的算法，用于查找最短路径并根据您的代码 无法跟踪您已经访问过的节点。因此，如果图中存在循环，这会导致无限递归。要解决这个问题，只需保留一个已访问过的

Set

。比如：

public int shortestDistance(char startTown, char endTown, char currentTown, int distance, int step, Set<Character> visited) {
    if (currentTown == endTown && step != 0) {
        return distance;
    }

    visited.add(currentTown);

    int shortestDistance = Integer.MAX_VALUE;
    for (char nextTown : graph.get(currentTown).keySet()) {
        if (!visited.contains(nextTown)) {
            shortestDistance = Math.min(shortestDistance, shortestDistance(startTown, endTown, nextTown,
                    distance + graph.get(currentTown).get(nextTown), step + 1, visited));
        }
    }

    visited.remove(currentTown);

    return shortestDistance;
}