如何在for循环中结合递归修改Java代码求无权重有向图最短路径

实现思路 #

你原有代码的问题是遍历邻居节点时遇到第一个可达节点就直接返回结果，没有遍历所有可能路径计算最小值，且修改邻接矩阵后没有回溯恢复，会影响后续路径计算。修改逻辑如下：

1. 初始化最短路径长度为极大值，用来存储所有合法路径的长度
2. 遍历所有邻居节点时，每次递归前标记当前边为已访问避免成环重复遍历，递归结束后恢复边的原始值（回溯，保证其他路径可以正常使用这条边）
3. 收集所有可达路径的长度，筛选出最小值返回，如果没有可达路径返回-1

修改后的核心逻辑（替换你原来的代码段） #

if (m[i][j] == 0) {
    int minLen = Integer.MAX_VALUE;
    int n = m.length;
    for (int k = 0; k < n; k++) {
        if (m[i][k] == 1) {
            // 标记边已访问，避免走环
            m[i][k] = 0;
            int subLen = findShortestPath(m, k, j);
            // 回溯恢复边的状态
            m[i][k] = 1;
            // 只统计合法路径的长度
            if (subLen != -1) {
                minLen = Math.min(minLen, 1 + subLen);
            }
        }
    }
    // 判断是否存在合法路径
    return minLen == Integer.MAX_VALUE ? -1 : minLen;
}

完整可运行代码 #

需要提前导入java.util.Arrays：

import java.util.Arrays;

public class ShortestPath {
    // 保留你原有findPath方法用于前置可达性判断，没有实现的话可以直接删掉这段和对应的调用
    private static int findPath(int[][] m, int i, int j) {
        boolean[] visited = new boolean[m.length];
        return dfsCheck(m, i, j, visited) ? 1 : 0;
    }

    private static boolean dfsCheck(int[][] m, int i, int j, boolean[] visited) {
        if (i == j) return true;
        visited[i] = true;
        for (int k = 0; k < m.length; k++) {
            if (m[i][k] == 1 && !visited[k]) {
                if (dfsCheck(m, k, j, visited)) return true;
            }
        }
        return false;
    }

    public static int findShortestPath(int[][] m, int i, int j) {
        if (i == j) return 0;
        // 前置可达性判断可直接删除，后续逻辑本身会识别无路径场景返回-1
        if (findPath(m, i, j) == 0) return -1;
        if (m[i][j] == 1) return 1;

        if (m[i][j] == 0) {
            int minLen = Integer.MAX_VALUE;
            int n = m.length;
            for (int k = 0; k < n; k++) {
                if (m[i][k] == 1) {
                    m[i][k] = 0;
                    int subLen = findShortestPath(m, k, j);
                    m[i][k] = 1;
                    if (subLen != -1) {
                        minLen = Math.min(minLen, 1 + subLen);
                    }
                }
            }
            return minLen == Integer.MAX_VALUE ? -1 : minLen;
        }
        return -1;
    }

    public static void main(String[] args) {
        // 测试用例1
        int[][] m1 = {{0,0,0},{0,0,0},{0,0,0}};
        System.out.println(findShortestPath(m1, 0,1)); // 输出-1
        // 测试用例2
        System.out.println(findShortestPath(m1,1,1)); // 输出0
        // 测试用例3
        int[][] m3 = {{0,1,0,0},{0,0,1,0},{0,0,0,1},{1,0,0,0}};
        System.out.println(findShortestPath(m3,0,2)); // 输出2
        // 测试用例4
        int[][] m4 = {{0,1,0,1},{0,0,0,1},{0,0,0,0},{0,0,1,0}};
        System.out.println(findShortestPath(m4,0,2)); // 输出2
    }
}

额外说明 #

对于无权重有向图的最短路径场景，你也可以选择BFS算法实现，时间复杂度更低，BFS天然适配无权重图的最短路径求解，不需要回溯也不需要遍历所有路径。

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