1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

贪心选择决策树示意图：

                   开始
                    |
            [做出贪心选择]
                    |
                子问题1
                    |
            [做出贪心选择]
                    |
                子问题2
                    |
                   ...
                    |
            [做出贪心选择]
                    |
                  结束

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class GreedyTemplate {
    public int greedy(int[] input) {
        // 1. 初始化
        int result = 0;

        // 2. 排序（如果需要）
        Arrays.sort(input);

        // 3. 贪心选择
        for (int i = 0; i < input.length; i++) {
            if (canSelect(input[i])) {
                // 做出贪心选择
                result += select(input[i]);
            }
        }

        return result;
    }

    private boolean canSelect(int item) {
        // 判断是否可以选择该项
        return true;
    }

    private int select(int item) {
        // 执行选择操作
        return item;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public class CoinChange {
    /**
     * 贪心算法解决零钱兑换（仅适用于标准币制）
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(1)
     */
    public int coinChangeGreedy(int[] coins, int amount) {
        // 按面额从大到小排序
        Arrays.sort(coins);
        reverse(coins);

        int count = 0;
        int i = 0;

        while (amount > 0 && i < coins.length) {
            if (amount >= coins[i]) {
                // 计算当前面额可以使用的最大数量
                int num = amount / coins[i];
                count += num;
                amount -= num * coins[i];
            }
            i++;
        }

        return amount == 0 ? count : -1;
    }

    private void reverse(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        CoinChange solution = new CoinChange();
        int[] coins = {1, 5, 10, 25};
        int amount = 67;

        System.out.println("最少硬币数：" + solution.coinChangeGreedy(coins, amount));
        // 输出：最少硬币数：6 (25*2 + 10*1 + 5*1 + 1*2)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

public class ActivitySelection {
    static class Activity {
        int start;
        int end;
        int index;

        Activity(int start, int end, int index) {
            this.start = start;
            this.end = end;
            this.index = index;
        }
    }

    /**
     * 活动选择问题 - 贪心算法
     * 策略：按结束时间排序，每次选择最早结束的活动
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     */
    public List<Integer> activitySelection(int[] start, int[] end) {
        int n = start.length;
        List<Activity> activities = new ArrayList<>();

        // 创建活动列表
        for (int i = 0; i < n; i++) {
            activities.add(new Activity(start[i], end[i], i));
        }

        // 按结束时间排序
        activities.sort((a, b) -> a.end - b.end);

        List<Integer> selected = new ArrayList<>();
        int lastEndTime = 0;

        for (Activity activity : activities) {
            // 如果当前活动的开始时间不早于上一个活动的结束时间
            if (activity.start >= lastEndTime) {
                selected.add(activity.index);
                lastEndTime = activity.end;
            }
        }

        return selected;
    }

    public static void main(String[] args) {
        ActivitySelection solution = new ActivitySelection();

        int[] start = {1, 3, 0, 5, 8, 5};
        int[] end = {2, 4, 6, 7, 9, 9};

        List<Integer> result = solution.activitySelection(start, end);
        System.out.println("选中的活动索引：" + result);

        // 打印选中的活动详情
        System.out.println("选中的活动详情：");
        for (int i : result) {
            System.out.println("活动" + i + ": [" + start[i] + ", " + end[i] + "]");
        }
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

public class HuffmanCoding {
    static class Node implements Comparable<Node> {
        char ch;
        int freq;
        Node left, right;

        Node(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
        }

        Node(int freq, Node left, Node right) {
            this.ch = '\0'; // 内部节点
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Node other) {
            return this.freq - other.freq;
        }

        boolean isLeaf() {
            return left == null && right == null;
        }
    }

    /**
     * 构建霍夫曼树
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     */
    public Node buildHuffmanTree(char[] chars, int[] freq) {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        // 将所有字符加入优先队列
        for (int i = 0; i < chars.length; i++) {
            pq.offer(new Node(chars[i], freq[i]));
        }

        // 构建霍夫曼树
        while (pq.size() > 1) {
            Node node1 = pq.poll();
            Node node2 = pq.poll();

            Node merged = new Node(node1.freq + node2.freq, node1, node2);
            pq.offer(merged);
        }

        return pq.poll();
    }

    /**
     * 生成霍夫曼编码
     */
    public Map<Character, String> generateCodes(Node root) {
        Map<Character, String> codes = new HashMap<>();
        if (root != null) {
            if (root.isLeaf()) {
                codes.put(root.ch, "0"); // 只有一个字符的特殊情况
            } else {
                generateCodes(root, "", codes);
            }
        }
        return codes;
    }

    private void generateCodes(Node node, String code, Map<Character, String> codes) {
        if (node.isLeaf()) {
            codes.put(node.ch, code);
        } else {
            generateCodes(node.left, code + "0", codes);
            generateCodes(node.right, code + "1", codes);
        }
    }

    public static void main(String[] args) {
        HuffmanCoding huffman = new HuffmanCoding();

        char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
        int[] freq = {5, 9, 12, 13, 16, 45};

        Node root = huffman.buildHuffmanTree(chars, freq);
        Map<Character, String> codes = huffman.generateCodes(root);

        System.out.println("霍夫曼编码：");
        for (Map.Entry<Character, String> entry : codes.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 计算平均编码长度
        double avgLength = 0;
        int totalFreq = Arrays.stream(freq).sum();
        for (int i = 0; i < chars.length; i++) {
            avgLength += (freq[i] * codes.get(chars[i]).length()) / (double) totalFreq;
        }
        System.out.printf("平均编码长度：%.2f\n", avgLength);
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

public class FractionalKnapsack {
    static class Item {
        int value;
        int weight;
        double ratio; // 价值密度

        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
            this.ratio = (double) value / weight;
        }
    }

    /**
     * 分数背包问题 - 贪心算法
     * 策略：按价值密度排序，优先选择价值密度高的物品
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     */
    public double fractionalKnapsack(int[] values, int[] weights, int capacity) {
        int n = values.length;
        Item[] items = new Item[n];

        // 创建物品列表并计算价值密度
        for (int i = 0; i < n; i++) {
            items[i] = new Item(values[i], weights[i]);
        }

        // 按价值密度降序排序
        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));

        double maxValue = 0;
        int currentCapacity = capacity;

        for (Item item : items) {
            if (currentCapacity >= item.weight) {
                // 完全装入该物品
                maxValue += item.value;
                currentCapacity -= item.weight;
            } else if (currentCapacity > 0) {
                // 部分装入该物品
                maxValue += item.value * ((double) currentCapacity / item.weight);
                break;
            }
        }

        return maxValue;
    }

    /**
     * 详细版本，显示装入过程
     */
    public void fractionalKnapsackDetailed(int[] values, int[] weights, int capacity) {
        int n = values.length;
        Item[] items = new Item[n];

        for (int i = 0; i < n; i++) {
            items[i] = new Item(values[i], weights[i]);
        }

        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));

        System.out.println("物品按价值密度排序：");
        for (int i = 0; i < items.length; i++) {
            System.out.printf("物品%d: 价值=%d, 重量=%d, 密度=%.2f\n",
                i, items[i].value, items[i].weight, items[i].ratio);
        }

        double maxValue = 0;
        int currentCapacity = capacity;

        System.out.println("\n装入过程：");
        for (int i = 0; i < items.length; i++) {
            if (currentCapacity >= items[i].weight) {
                maxValue += items[i].value;
                currentCapacity -= items[i].weight;
                System.out.printf("完全装入物品%d，剩余容量=%d，当前价值=%.2f\n",
                    i, currentCapacity, maxValue);
            } else if (currentCapacity > 0) {
                double fraction = (double) currentCapacity / items[i].weight;
                maxValue += items[i].value * fraction;
                System.out.printf("部分装入物品%d（%.2f%%），最终价值=%.2f\n",
                    i, fraction * 100, maxValue);
                break;
            }
        }
    }

    public static void main(String[] args) {
        FractionalKnapsack solution = new FractionalKnapsack();

        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;

        double result = solution.fractionalKnapsack(values, weights, capacity);
        System.out.println("最大价值：" + result);

        System.out.println("\n详细过程：");
        solution.fractionalKnapsackDetailed(values, weights, capacity);
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

public class IntervalScheduling {
    static class Interval {
        int start;
        int end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "[" + start + ", " + end + "]";
        }
    }

    /**
     * 区间调度问题 - 贪心算法
     * 策略：按结束时间排序，每次选择最早结束的区间
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(1)
     */
    public int intervalScheduling(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // 按结束时间排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int count = 1;
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间的开始时间不早于上一个区间的结束时间
            if (intervals[i][0] >= end) {
                count++;
                end = intervals[i][1];
            }
        }

        return count;
    }

    /**
     * 返回具体的调度方案
     */
    public List<Interval> getSchedule(int[][] intervals) {
        List<Interval> result = new ArrayList<>();
        if (intervals.length == 0) return result;

        // 创建区间对象并排序
        List<Interval> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(new Interval(interval[0], interval[1]));
        }

        list.sort((a, b) -> a.end - b.end);

        result.add(list.get(0));
        int end = list.get(0).end;

        for (int i = 1; i < list.size(); i++) {
            if (list.get(i).start >= end) {
                result.add(list.get(i));
                end = list.get(i).end;
            }
        }

        return result;
    }

    /**
     * 区间调度的变种：最小会议室数量
     */
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // 将开始和结束时间分别排序
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];

        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }

        Arrays.sort(starts);
        Arrays.sort(ends);

        int rooms = 0;
        int maxRooms = 0;
        int i = 0, j = 0;

        while (i < starts.length) {
            if (starts[i] < ends[j]) {
                rooms++;
                maxRooms = Math.max(maxRooms, rooms);
                i++;
            } else {
                rooms--;
                j++;
            }
        }

        return maxRooms;
    }

    public static void main(String[] args) {
        IntervalScheduling solution = new IntervalScheduling();

        int[][] intervals = {{1, 3}, {2, 4}, {3, 6}, {5, 7}, {8, 9}};

        System.out.println("最多可调度区间数：" + solution.intervalScheduling(intervals));

        List<Interval> schedule = solution.getSchedule(intervals);
        System.out.println("调度方案：" + schedule);

        System.out.println("需要的最少会议室数：" + solution.minMeetingRooms(intervals));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * 活动选择问题的正确性证明示例
 * 证明思路：任何最优解都可以通过交换得到我们的贪心解
 */
public class ProofExample {
    /**
     * 证明贪心选择的正确性
     *
     * 定理：对于活动选择问题，按结束时间排序并选择最早结束的活动是最优的
     *
     * 证明：
     * 设A = {a1, a2, ..., ak}是某个最优解
     * 设G = {g1, g2, ..., gm}是贪心算法的解
     *
     * 如果A != G，考虑第一个不同的活动
     * 设gi是贪心算法选择的第i个活动，ai是最优解中对应位置的活动
     *
     * 由于贪心算法选择最早结束的活动，有：gi.end <= ai.end
     *
     * 我们可以将最优解中的ai替换为gi，得到新解A'
     * A'仍然是可行解（因为gi结束更早，不会与后续活动冲突）
     * |A'| = |A|，所以A'也是最优解
     *
     * 重复这个过程，最终可以得到贪心解G也是最优解
     */
    public void proofByExchange() {
        System.out.println("交换论证法证明贪心算法正确性：");
        System.out.println("1. 假设存在最优解A不同于贪心解G");
        System.out.println("2. 找到第一个不同的选择");
        System.out.println("3. 证明可以用贪心选择替换最优解中的选择");
        System.out.println("4. 替换后仍为最优解");
        System.out.println("5. 重复此过程直到得到贪心解");
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * 归纳法证明贪心算法正确性
 */
public class InductionProof {
    /**
     * 证明分数背包问题贪心算法的正确性
     *
     * 基础情况：n=1时，只有一个物品，贪心算法显然正确
     *
     * 归纳假设：对于k个物品，贪心算法得到最优解
     *
     * 归纳步骤：对于k+1个物品，设贪心算法选择价值密度最高的物品x
     * - 如果x完全装入，剩余问题是k个物品的子问题，由归纳假设知贪心算法最优
     * - 如果x部分装入，则其他物品都不能装入，贪心选择显然最优
     */
    public void proofByInduction() {
        System.out.println("归纳法证明贪心算法正确性：");
        System.out.println("1. 基础情况：问题规模为1时算法正确");
        System.out.println("2. 归纳假设：规模为k时算法正确");
        System.out.println("3. 归纳步骤：证明规模为k+1时算法仍正确");
        System.out.println("4. 结合贪心选择性质完成证明");
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

public class AlgorithmChoice {
    /**
     * 何时选择贪心算法
     */
    public void whenToUseGreedy() {
        System.out.println("选择贪心算法的情况：");
        System.out.println("1. 问题具有贪心选择性质");
        System.out.println("2. 问题具有最优子结构");
        System.out.println("3. 局部最优能导致全局最优");
        System.out.println("4. 对效率要求较高");

        System.out.println("\n贪心算法适用的问题类型：");
        System.out.println("- 活动选择问题");
        System.out.println("- 分数背包问题");
        System.out.println("- 霍夫曼编码");
        System.out.println("- 最小生成树（Kruskal, Prim）");
        System.out.println("- 单源最短路径（Dijkstra）");
    }

    /**
     * 何时选择动态规划
     */
    public void whenToUseDP() {
        System.out.println("选择动态规划的情况：");
        System.out.println("1. 问题具有最优子结构");
        System.out.println("2. 子问题重叠");
        System.out.println("3. 贪心选择不能得到最优解");
        System.out.println("4. 需要考虑所有可能的选择");

        System.out.println("\n动态规划适用的问题类型：");
        System.out.println("- 0-1背包问题");
        System.out.println("- 最长公共子序列");
        System.out.println("- 编辑距离");
        System.out.println("- 硬币找零（非标准币制）");
        System.out.println("- 股票买卖问题");
    }

    /**
     * 对比示例：背包问题
     */
    public void knapsackComparison() {
        System.out.println("背包问题对比：");
        System.out.println("\n分数背包（可分割）：");
        System.out.println("- 贪心算法：按价值密度排序，总是选择密度最高的");
        System.out.println("- 时间复杂度：O(n log n)");
        System.out.println("- 能得到最优解");

        System.out.println("\n0-1背包（不可分割）：");
        System.out.println("- 动态规划：考虑每个物品选或不选的所有情况");
        System.out.println("- 时间复杂度：O(nW)");
        System.out.println("- 贪心算法不能保证最优解");
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

public class TaskScheduler {
    static class Task {
        String name;
        int priority;
        int duration;
        int deadline;

        Task(String name, int priority, int duration, int deadline) {
            this.name = name;
            this.priority = priority;
            this.duration = duration;
            this.deadline = deadline;
        }
    }

    /**
     * 基于优先级的任务调度
     * 贪心策略：优先执行高优先级任务
     */
    public List<Task> scheduleBypriority(List<Task> tasks) {
        List<Task> schedule = new ArrayList<>(tasks);

        // 按优先级降序排序
        schedule.sort((a, b) -> b.priority - a.priority);

        return schedule;
    }

    /**
     * 基于截止时间的任务调度（Earliest Deadline First）
     * 贪心策略：优先执行截止时间最早的任务
     */
    public List<Task> scheduleByDeadline(List<Task> tasks) {
        List<Task> schedule = new ArrayList<>(tasks);

        // 按截止时间升序排序
        schedule.sort((a, b) -> a.deadline - b.deadline);

        return schedule;
    }

    /**
     * 最短处理时间优先（Shortest Processing Time First）
     * 贪心策略：优先执行处理时间最短的任务
     */
    public List<Task> scheduleBySPT(List<Task> tasks) {
        List<Task> schedule = new ArrayList<>(tasks);

        // 按处理时间升序排序
        schedule.sort((a, b) -> a.duration - b.duration);

        return schedule;
    }

    public static void main(String[] args) {
        TaskScheduler scheduler = new TaskScheduler();

        List<Task> tasks = Arrays.asList(
            new Task("任务A", 3, 4, 10),
            new Task("任务B", 1, 2, 6),
            new Task("任务C", 2, 6, 8),
            new Task("任务D", 3, 3, 12)
        );

        System.out.println("原始任务列表：");
        tasks.forEach(task -> System.out.println(task.name + " - 优先级:" +
            task.priority + ", 时长:" + task.duration + ", 截止:" + task.deadline));

        System.out.println("\n按优先级调度：");
        scheduler.scheduleBypriority(tasks).forEach(task -> System.out.print(task.name + " "));

        System.out.println("\n\n按截止时间调度：");
        scheduler.scheduleByDeadline(tasks).forEach(task -> System.out.print(task.name + " "));

        System.out.println("\n\n按处理时间调度：");
        scheduler.scheduleBySPT(tasks).forEach(task -> System.out.print(task.name + " "));
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

public class NetworkRouting {
    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    /**
     * Dijkstra算法 - 单源最短路径
     * 贪心策略：每次选择距离最近的未访问节点
     * 时间复杂度：O((V + E) log V)
     */
    public int[] dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];

            if (visited[u]) continue;
            visited[u] = true;

            // 更新邻接节点的距离
            for (Edge edge : graph.get(u)) {
                int v = edge.to;
                int weight = edge.weight;

                if (!visited[v] && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }

        return dist;
    }

    /**
     * 构建路由表
     */
    public void buildRoutingTable(List<List<Edge>> graph, int router) {
        int[] distances = dijkstra(graph, router);

        System.out.println("路由器 " + router + " 的路由表：");
        System.out.println("目标\t距离\t下一跳");
        System.out.println("--------------------");

        for (int i = 0; i < distances.length; i++) {
            if (i != router) {
                String distance = distances[i] == Integer.MAX_VALUE ? "∞" : String.valueOf(distances[i]);
                System.out.println(i + "\t" + distance + "\t" + getNextHop(graph, router, i));
            }
        }
    }

    private int getNextHop(List<List<Edge>> graph, int start, int target) {
        // 简化版本，实际实现需要记录路径
        for (Edge edge : graph.get(start)) {
            if (edge.to == target) {
                return target;
            }
        }
        return -1; // 需要更复杂的路径重构
    }

    public static void main(String[] args) {
        NetworkRouting routing = new NetworkRouting();

        // 构建网络图
        int n = 5;
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 添加边（双向）
        addBidirectionalEdge(graph, 0, 1, 4);
        addBidirectionalEdge(graph, 0, 2, 2);
        addBidirectionalEdge(graph, 1, 2, 1);
        addBidirectionalEdge(graph, 1, 3, 5);
        addBidirectionalEdge(graph, 2, 3, 8);
        addBidirectionalEdge(graph, 2, 4, 10);
        addBidirectionalEdge(graph, 3, 4, 2);

        // 从节点0开始的最短路径
        int[] distances = routing.dijkstra(graph, 0);
        System.out.println("从节点0到各节点的最短距离：");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("到节点" + i + ": " + distances[i]);
        }
    }

    private static void addBidirectionalEdge(List<List<Edge>> graph, int u, int v, int weight) {
        graph.get(u).add(new Edge(v, weight));
        graph.get(v).add(new Edge(u, weight));
    }
}