带权完全二叉树全节点最短路径：贪心与递归算法实现咨询

已实现Java代码生成指定规模的带权完全二叉树，采用两个数组存储：

• WN数组：存储节点权值，取值为1~20的随机整数
• WE二维数组：存储边权值，同样是1~20的随机整数

现需要开发贪心算法与递归算法，求解该树中所有节点间的最短路径，以下是实现指导及已有的树生成代码。

import java.util.Arrays;

public class WeightedBinaryTreeGenerator {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(randWN(9)));
        int[][] qq = randWE(9);
        for (int[] row : qq) {
            System.out.println(Arrays.toString(row));
        }
    }

    public static int[] randWN(int size) {
        int[] WN = new int[size];
        for (int i = 0; i < WN.length; i++) {
            WN[i] = getRandomNumber(1, 20);
        }
        return WN;
    }

    public static int[][] randWE(int size) {
        int counter = 0;
        int iterator = 0;
        int[][] WE = new int[size][size];
        for (int i = 0; i < WE.length; i++) {
            for (int j = 0; j < WE[size - 1].length; j++) {
                if (j > iterator && counter < 2) {
                    WE[i][j] = getRandomNumber(1, 20);
                    WE[j][i] = WE[i][j]; // 补充无向边的反向权值，保证二叉树边双向可通行
                    counter++;
                    iterator++;
                }
            }
            counter = 0;
        }
        return WE;
    }

    public static int getRandomNumber(int min, int max) {
        return (int) ((Math.random() * (max - min)) + min);
    }
}

由于树中不存在环，任意两个节点间的最短路径是唯一的。这里用贪心策略逐个计算每个节点到其他所有节点的最短路径：

核心思路 #

以每个节点为起点，每次选择当前已访问集合中到起点路径最短的相邻未访问节点，更新该节点的路径长度，直到所有节点都被访问。因树的特性，每个节点仅被访问一次，时间复杂度为O(n²)，适合小规模完全二叉树。

代码实现 #

import java.util.Arrays;

public class GreedyShortestPath {
    // 计算从start节点到所有节点的最短路径
    public static int[] greedyShortestPath(int[][] WE, int start) {
        int n = WE.length;
        int[] dist = new int[n]; // 存储start到各节点的最短路径长度
        boolean[] visited = new boolean[n]; // 标记节点是否已访问

        // 初始化：起点到自身距离为0，其他设为无穷大
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int i = 0; i < n; i++) {
            // 找到当前未访问节点中距离start最近的节点u
            int u = -1;
            int minDist = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    u = j;
                }
            }

            if (u == -1) break; // 树中所有节点都可达，此分支仅作鲁棒性处理
            visited[u] = true;

            // 更新u的相邻节点的距离
            for (int v = 0; v < n; v++) {
                if (!visited[v] && WE[u][v] != 0 && dist[u] != Integer.MAX_VALUE) {
                    int newDist = dist[u] + WE[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                    }
                }
            }
        }
        return dist;
    }

    // 计算所有节点间的最短路径，返回二维数组：dist[i][j]表示i到j的最短路径长度
    public static int[][] allPairsGreedy(int[][] WE) {
        int n = WE.length;
        int[][] allDist = new int[n][n];
        for (int i = 0; i < n; i++) {
            allDist[i] = greedyShortestPath(WE, i);
        }
        return allDist;
    }

    public static void main(String[] args) {
        int[][] WE = WeightedBinaryTreeGenerator.randWE(9);
        int[][] allDist = allPairsGreedy(WE);
        System.out.println("所有节点间的最短路径：");
        for (int[] row : allDist) {
            System.out.println(Arrays.toString(row));
        }
    }
}

利用树的递归结构，从每个节点出发，递归遍历其所有相邻节点（父节点、左子节点、右子节点），记录路径长度即可。

核心思路 #

对于任意节点current：

1. 递归访问其所有未被访问过的相邻节点neighbor
2. 更新neighbor到起点的路径长度为current到起点的长度 + 边权WE[current][neighbor]
3. 标记neighbor已访问，继续递归neighbor的相邻节点

代码实现 #

import java.util.Arrays;

public class RecursiveShortestPath {
    // 递归计算从start到所有节点的最短路径
    private static void dfs(int[][] WE, int current, int currentDist, int[] dist, boolean[] visited) {
        dist[current] = currentDist;
        visited[current] = true;

        // 遍历所有相邻节点
        for (int v = 0; v < WE.length; v++) {
            if (WE[current][v] != 0 && !visited[v]) {
                dfs(WE, v, currentDist + WE[current][v], dist, visited);
            }
        }
    }

    public static int[] recursiveShortestPath(int[][] WE, int start) {
        int n = WE.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        dfs(WE, start, 0, dist, visited);
        return dist;
    }

    // 计算所有节点间的最短路径
    public static int[][] allPairsRecursive(int[][] WE) {
        int n = WE.length;
        int[][] allDist = new int[n][n];
        for (int i = 0; i < n; i++) {
            allDist[i] = recursiveShortestPath(WE, i);
        }
        return allDist;
    }

    public static void main(String[] args) {
        int[][] WE = WeightedBinaryTreeGenerator.randWE(9);
        int[][] allDist = allPairsRecursive(WE);
        System.out.println("所有节点间的最短路径：");
        for (int[] row : allDist) {
            System.out.println(Arrays.toString(row));
        }
    }
}

1. 树的特性：完全二叉树中任意两个节点之间存在唯一路径，因此最短路径就是这条唯一路径的权值和，两种算法本质都是遍历路径并累加权值。
2. 贪心算法：采用类似Dijkstra的贪心策略，适合理解最短路径的贪心思想，后续扩展到带环图也能复用思路。
3. 递归算法：利用树的递归结构实现深度优先遍历，代码更简洁，符合树的天然递归特性。

内容的提问来源于stack exchange，提问作者Furkan Şenoğlu