Java递归实现最短路径时遭遇无限递归问题求助

你的问题核心是未在递归中跟踪已访问节点，导致无向边（如C↔D）引发无限递归。以下是具体的修改方案：

关键修改思路 #

在递归函数中加入已访问城镇集合，每次递归时检查下一个城镇是否已在当前路径中，避免重复进入同一节点形成循环。注意要为每个递归分支创建独立的访问集合，不能共享同一集合（否则会破坏其他分支的遍历逻辑）。

修改后的代码 #

public int shortestDistance(char startTown, char endTown, char currentTown, int distance, int step, Set<Character> visited) {
    // 到达终点且不是初始步骤（避免起点直接等于终点的无效路径）
    if (currentTown == endTown && step != 0) {
        return distance;
    }

    int shortestDistance = Integer.MAX_VALUE;
    // 遍历当前城镇的所有邻接城镇
    for (char nextTown : graph.get(currentTown).keySet()) {
        // 跳过已访问的城镇，避免循环
        if (visited.contains(nextTown)) {
            continue;
        }
        // 创建新的访问集合，添加当前城镇（因为当前路径已经过它）
        Set<Character> newVisited = new HashSet<>(visited);
        newVisited.add(currentTown);
        // 递归计算子路径的最短距离
        int subDistance = shortestDistance(startTown, endTown, nextTown,
                distance + graph.get(currentTown).get(nextTown), step + 1, newVisited);
        // 更新最短距离（注意处理子路径无有效解的情况）
        if (subDistance != Integer.MAX_VALUE) {
            shortestDistance = Math.min(shortestDistance, subDistance);
        }
    }
    return shortestDistance;
}

初始调用方式 #

调用时需要传入包含起始城镇的访问集合：

Set<Character> initialVisited = new HashSet<>();
initialVisited.add(startTown); // 这里startTown是'B'
int result = shortestDistance('B', 'B', 'B', 0, 0, initialVisited);

常见错误说明（为什么之前的List/Set没生效） #

• 共享同一集合：如果递归中直接修改原List/Set（比如add后没回溯remove），会导致其他分支的访问记录被错误污染，限制了正常路径的遍历。
• 未正确检查下一个节点：可能只检查了当前节点是否在集合中，而非下一个节点，导致循环无法被拦截。
• 初始集合未包含起始节点：起始节点本身需要被标记为已访问，否则递归第一步就可能回头（比如B->...->B的路径中，不能直接从B再回到B，但允许经过其他节点后回到B）。

验证最短路径 #

以你的输入为例，修改后的代码会找到路径B→C→E→B，总距离4+2+3=9，这正是正确的最短路径。

内容的提问来源于stack exchange，提问作者Wragnam