前言

本文主要讲解8种算法经典问题。

数据结构与算法文章列表

数据结构与算法文章列表: 点击此处跳转查看

1 分治算法经典问题：汉诺塔问题

汉诺塔问题（Tower of Hanoi Problem） 是一个经典的递归和分治算法问题。问题描述如下：

有三根柱子（标记为A、B和C），开始时，在柱子A上有一堆按照从上到下递增顺序摆放的圆盘。目标是将所有圆盘从柱子A移动到柱子C，每次只能移动一个圆盘，并且在移动过程中，任何时候都不能让大圆盘放在小圆盘上面。

要解决汉诺塔问题，我们可以使用递归和分治的思想：将问题分解为子问题，然后递归地解决子问题。

实现步骤：

定义一个递归函数，该函数接受以下参数：
n：要移动的圆盘数量。
source：表示初始柱子。
target：表示目标柱子。
auxiliary：表示辅助柱子。
在函数内部，通过递归进行以下步骤：
a. 如果 n == 1，直接将圆盘从 source 移动到 target。b. 否则，先将 n-1 个圆盘从 source 经由 target 移动到 auxiliary。c. 然后将第 n 个圆盘从 source 移动到 target。d. 最后，将 n-1 个圆盘从 auxiliary 经由 source 移动到 target。
调用递归函数，将所有圆盘从柱子A移动到柱子C。

完整代码：

java复制代码public class TowerOfHanoi {
    public static void towerOfHanoi(int n, char source, char target, char auxiliary) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + target);
            return;
        }
        towerOfHanoi(n - 1, source, auxiliary, target);
        System.out.println("Move disk " + n + " from " + source + " to " + target);
        towerOfHanoi(n - 1, auxiliary, target, source);
    }
    public static void main(String[] args) {
        int numberOfDisks = 3;
        towerOfHanoi(numberOfDisks, 'A', 'C', 'B');
    }
}

运行结果：

css复制代码Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

总结：

汉诺塔问题是一个经典的递归和分治算法问题。通过将问题分解为子问题，并逐步递归解决子问题，我们可以将所有圆盘从一个柱子移动到另一个柱子。该问题的递归解法十分简洁，但效率并不高，因为存在很多重复的子问题,不管怎样，汉诺塔问题仍然是一个很好的示例，用于理解递归和分治算法的基本原理。

2 动态规划算法经典问题：背包问题

背包问题是一个经典的动态规划问题。在背包问题中，有一个固定容量的背包，以及一组物品，每个物品都有自己的重量和价值。目标是将物品放入背包中，使得在不超过背包容量的前提下，背包中物品的总价值最大化。

在背包问题中，有三种常见的变体：0-1背包问题、完全背包问题和多重背包问题。

2.1 0-1背包问题

0-1背包问题是背包问题的经典变体。在这个问题中，给定一个背包容量为C的背包和n个物品，每个物品有对应的价值value和重量weight。要求在不超过背包容量的情况下，选择物品使得总价值最大，且每个物品只能选择一次放入背包。

实现步骤：

定义动态规划数组：创建一个dp二维数组，其中dp[i][j]表示在前i个物品中选择，且背包容量为j时的最大总价值。
初始化：将dp[i][0]和dp[0][j]都初始化为0，表示背包容量为0或没有物品可选时，获得的最大总价值为0。
状态转移方程：遍历每个物品，更新dp[i][j]的值，逐步求解dp[n][C]。

现在，我们来实现这个算法：

java复制代码public class Knapsack01Problem {
    public static int knapsack01(int C, int[] values, int[] weights) {
        int n = values.length;
        int[][] dp = new int[n + 1][C + 1];
        // 初始化
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= C; j++) {
            dp[0][j] = 0;
        }
        // 计算dp数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= C; j++) {
                if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][C];
    }
    public static void main(String[] args) {
        int C = 10;
        int[] values = {10, 40, 30, 50};
        int[] weights = {5, 4, 6, 3};
        int maxTotalValue = knapsack01(C, values, weights);
        System.out.println("Maximum total value in the knapsack: " + maxTotalValue);
    }
}

运行结果：

yaml复制代码Maximum total value in the knapsack: 90

总结：

0-1背包问题是另一个动态规划中的经典问题。通过定义二维状态转移数组和状态转移方程，我们可以有效地解决这类问题。在上面的代码中，我们使用了dp二维数组来保存在前i个物品中选择，且背包容量为j时的最大总价值。通过两重循环，我们逐步求解最终的dp[n][C]，得到背包容量为C时可以获得的最大总价值。

和完全背包问题一样，0-1背包问题的动态规划时间复杂度也是O(C * n)，其中C是背包的容量，n是物品的个数。

2.2 完全背包问题

给定一个背包容量为C的背包和n个物品，每个物品有对应的价值value和重量weight。要求在不超过背包容量的情况下，选择物品使得总价值最大，且每个物品可以选择无限次放入背包。

实现步骤：

定义动态规划数组：创建一个dp数组，其中dp[i]表示背包容量为i时，可以获得的最大总价值。
初始化：将dp[0]初始化为0，表示背包容量为0时，获得的最大总价值为0。
状态转移方程：遍历每个物品，更新dp[i]的值，逐步求解dp[C]。

现在，我们来实现这个算法：

java复制代码public class KnapsackProblem {
    public static int knapsack(int C, int[] values, int[] weights) {
        int n = values.length;
        int[] dp = new int[C + 1];
        // 初始化
        dp[0] = 0;
        // 计算dp数组
        for (int i = 1; i <= C; i++) {
            for (int j = 0; j < n; j++) {
                if (weights[j] <= i) {
                    dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
                }
            }
        }
        return dp[C];
    }
    public static void main(String[] args) {
        int C = 10;
        int[] values = {10, 40, 30, 50};
        int[] weights = {5, 4, 6, 3};
        int maxTotalValue = knapsack(C, values, weights);
        System.out.println("Maximum total value in the knapsack: " + maxTotalValue);
    }
}

运行结果：

yaml复制代码Maximum total value in the knapsack: 100

总结：

完全背包问题是动态规划中经典的问题之一。通过定义状态转移数组和状态转移方程，我们可以有效地解决这类问题。在上面的代码中，我们使用了一维数组dp来保存不同容量下的最大总价值。通过两重循环，我们逐步求解最终的dp[C]，得到背包容量为C时可以获得的最大总价值。

动态规划的时间复杂度是O(C * n)，其中C是背包的容量，n是物品的个数。

2.3 多重背包问题

多重背包问题是背包问题的另一种变体。在这个问题中，给定一个背包容量为C的背包和n个物品，每个物品有对应的价值value、重量weight和可选数量count。要求在不超过背包容量的情况下，选择物品使得总价值最大，且每个物品可选数量不能超过count次。

实现步骤：

定义动态规划数组：创建一个dp二维数组，其中dp[i][j]表示在前i个物品中选择，且背包容量为j时的最大总价值。
初始化：将dp[i][0]和dp[0][j]都初始化为0，表示背包容量为0或没有物品可选时，获得的最大总价值为0。
状态转移方程：遍历每个物品，对于每个物品，我们需要考虑选择0个、1个、2个…直到count个，更新dp[i][j]的值，逐步求解dp[n][C]。

现在，我们来实现这个算法：

java复制代码public class MultipleKnapsackProblem {
    public static int multipleKnapsack(int C, int[] values, int[] weights, int[] counts) {
        int n = values.length;
        int[][] dp = new int[n + 1][C + 1];
        // 初始化
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= C; j++) {
            dp[0][j] = 0;
        }
        // 计算dp数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= C; j++) {
                for (int k = 0; k <= counts[i - 1] && k * weights[i - 1] <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * weights[i - 1]] + k * values[i - 1]);
                }
            }
        }
        return dp[n][C];
    }
    public static void main(String[] args) {
        int C = 10;
        int[] values = {10, 40, 30, 50};
        int[] weights = {5, 4, 6, 3};
        int[] counts = {2, 1, 2, 1};
        int maxTotalValue = multipleKnapsack(C, values, weights, counts);
        System.out.println("Maximum total value in the knapsack: " + maxTotalValue);
    }
}

运行结果：

yaml复制代码Maximum total value in the knapsack: 130

总结：

多重背包问题是0-1背包问题的一种变体。通过定义二维状态转移数组和状态转移方程，我们可以有效地解决这类问题。在上面的代码中，我们使用了dp二维数组来保存在前i个物品中选择，且背包容量为j时的最大总价值。通过三重循环，我们逐步求解最终的dp[n][C]，得到背包容量为C时可以获得的最大总价值。

多重背包问题的动态规划时间复杂度较高，为O(C * n * m)，其中C是背包的容量，n是物品的个数，m是物品的可选数量上限。

3 KMP算法经典问题：字符串匹配问题

字符串匹配问题是一个经典的算法问题，目标是在一个长字符串（称为主串）中查找一个子串是否出现，并返回其在主串中的位置。一种高效的字符串匹配算法是KMP算法（Knuth-Morris-Pratt算法），它能够在时间复杂度为O(n+m)内解决字符串匹配问题，其中n是主串的长度，m是子串的长度。

KMP算法的实现步骤：

计算部分匹配表（Partial Match Table） ：首先需要预处理子串，生成部分匹配表。部分匹配表是一个数组，记录了子串每个位置前缀的最长相同前缀后缀的长度。这个表的构建使用了动态规划的思想。
进行匹配：使用部分匹配表进行匹配，避免不必要的回溯，从而提高匹配效率。

KMP算法的详细步骤：

根据子串构建部分匹配表。
初始化两个指针：i指向主串，j指向子串。
从头开始遍历主串和子串：
a. 如果当前字符匹配成功，则同时移动两个指针继续匹配。b. 如果当前字符匹配失败，并且j不在子串的开头，根据部分匹配表回退j，继续与主串中的当前字符匹配。c. 如果当前字符匹配失败，并且j在子串的开头，则说明当前字符与子串的第一个字符不匹配，将i向后移动一位，继续匹配。

完整代码：

下面给出一个实现KMP算法的Java代码：

java复制代码public class KMPAlgorithm {
    private static int[] computePartialMatchTable(String pattern) {
        int[] table = new int[pattern.length()];
        table[0] = 0;
        int j = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = table[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            table[i] = j;
        }
        return table;
    }
    public static int search(String text, String pattern) {
        int[] table = computePartialMatchTable(pattern);
        int i = 0; // pointer for text
        int j = 0; // pointer for pattern
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }
            if (j == pattern.length()) {
                return i - j; // match found at index i-j
            } else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
                if (j != 0) {
                    j = table[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1; // match not found
    }
    public static void main(String[] args) {
        String text = "ABABABCABABABCABABABC";
        String pattern = "ABABC";
        int result = search(text, pattern);
        System.out.println("Pattern found at index: " + result);
    }
}

运行结果：

perl复制代码Pattern found at index: 5

总结：

KMP算法是一种高效的字符串匹配算法，通过预处理子串生成部分匹配表，在匹配时避免不必要的回溯，从而提高了匹配效率。相比朴素的字符串匹配算法，KMP算法的时间复杂度为O(n+m)，其中n是主串的长度，m是子串的长度。这使得KMP算法在实际应用中得到广泛的使用，特别是在大规模文本搜索和模式匹配等领域。

4 贪心算法经典问题：集合覆盖问题

集合覆盖问题是贪心算法的一个经典应用。在集合覆盖问题中，假设有一个全集，以及一些子集合，目标是找到最小数量的子集合，使得这些子集合的并集等于全集。换句话说，要用最少的子集合来覆盖全集。

贪心算法实现步骤：

初始化一个空的集合 selectedSet，用于存储所选的子集合。
从剩余未覆盖元素的全集中，选择一个能覆盖最多未覆盖元素的子集合，并将其加入 selectedSet。
重复步骤2，直到所有元素都被覆盖。

完整代码：

下面给出一个Java实现的集合覆盖问题的代码：

java复制代码import java.util.*;
public class SetCoverProblem {
    // 集合覆盖问题的贪心算法实现
    public static List<String> greedySetCover(Map<String, Set<String>> sets) {
        List<String> selectedSet = new ArrayList<>();
        // 复制原始集合，以避免修改输入参数
        Map<String, Set<String>> copySets = new HashMap<>(sets);
        // 当所有元素都被覆盖时结束循环
        while (!copySets.isEmpty()) {
            String maxSetKey = null;
            int maxUncoveredCount = 0;
            // 遍历子集合，找到能覆盖最多未覆盖元素的子集合
            for (Map.Entry<String, Set<String>> entry : copySets.entrySet()) {
                int uncoveredCount = countUncoveredElements(entry.getValue(), copySets);
                if (uncoveredCount > maxUncoveredCount) {
                    maxUncoveredCount = uncoveredCount;
                    maxSetKey = entry.getKey();
                }
            }
            // 将能覆盖最多未覆盖元素的子集合加入选中的集合中，并从剩余集合中移除已覆盖的元素
            selectedSet.add(maxSetKey);
            copySets.remove(maxSetKey);
            copySets.values().forEach(s -> s.removeAll(copySets.get(maxSetKey)));
        }
        return selectedSet;
    }
    // 计算集合中未被覆盖的元素数量
    private static int countUncoveredElements(Set<String> set, Map<String, Set<String>> sets) {
        Set<String> uncoveredElements = new HashSet<>(set);
        sets.values().forEach(uncoveredElements::removeAll);
        return uncoveredElements.size();
    }
    public static void main(String[] args) {
        // 假设有以下子集合
        Map<String, Set<String>> sets = new HashMap<>();
        sets.put("set1", new HashSet<>(Arrays.asList("a", "b", "c", "d")));
        sets.put("set2", new HashSet<>(Arrays.asList("a", "c", "e")));
        sets.put("set3", new HashSet<>(Arrays.asList("c", "d", "e")));
        sets.put("set4", new HashSet<>(Arrays.asList("b", "e")));
        List<String> selectedSet = greedySetCover(sets);
        System.out.println("Selected sets: " + selectedSet);
    }
}

运行结果：

ini复制代码Selected sets: [set1, set3, set4]

总结：

集合覆盖问题是一个经典的贪心算法应用。在解决集合覆盖问题时，我们使用贪心策略，每次选择能够覆盖最多未覆盖元素的子集合，直到所有元素都被覆盖。贪心算法虽然不能保证得到最优解，但在实际应用中，它通常能够得到近似的最优解，并且具有高效性。在集合覆盖问题中，贪心算法的时间复杂度取决于子集合的数量和元素的数量，通常是一个比较高效的解决方案。

5 普里姆算法经典问题：修路问题

修路问题是普里姆算法（Prim’s Algorithm）的一个经典应用。在修路问题中，给定一个连通的带权无向图，目标是找到一个最小生成树（Minimum Spanning Tree，简称MST），即通过修建若干条边连接所有节点，并且总权值最小。

普里姆算法实现步骤：

选择一个起始节点，将其加入最小生成树。
重复以下步骤，直到最小生成树包含了所有节点：
a. 从已构建的最小生成树中找到距离最近的节点（不在最小生成树中的节点）。b. 将该节点加入最小生成树，并将与其相邻的边加入边集合。c. 选择边集合中权值最小的边，并将其加入最小生成树。

完整代码：

下面给出一个Java实现的修路问题的代码：

java复制代码import java.util.*;
public class PrimAlgorithm {
    // 修路问题的普里姆算法实现
    public static List<Edge> primMST(List<Edge>[] graph, int startNode) {
        List<Edge> mst = new ArrayList<>(); // 最小生成树
        Set<Integer> visited = new HashSet<>(); // 已访问过的节点
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight)); // 用于选择最小边的优先队列
        // 从起始节点开始
        visited.add(startNode);
        // 将起始节点相邻的边加入优先队列
        for (Edge edge : graph[startNode]) {
            minHeap.offer(edge);
        }
        // 循环直到最小生成树包含所有节点
        while (visited.size() < graph.length) {
            Edge minEdge = minHeap.poll();
            // 如果另一个节点未访问过，则将其加入最小生成树，并将其相邻的边加入优先队列
            if (!visited.contains(minEdge.to)) {
                visited.add(minEdge.to);
                mst.add(minEdge);
                for (Edge edge : graph[minEdge.to]) {
                    if (!visited.contains(edge.to)) {
                        minHeap.offer(edge);
                    }
                }
            }
        }
        return mst;
    }
    public static void main(String[] args) {
        // 创建带权无向图
        int numNodes = 5;
        List<Edge>[] graph = new ArrayList[numNodes];
        for (int i = 0; i < numNodes; i++) {
            graph[i] = new ArrayList<>();
        }
        // 添加边
        graph[0].add(new Edge(0, 1, 2));
        graph[0].add(new Edge(0, 3, 6));
        graph[1].add(new Edge(1, 0, 2));
        graph[1].add(new Edge(1, 2, 3));
        graph[1].add(new Edge(1, 3, 8));
        graph[2].add(new Edge(2, 1, 3));
        graph[2].add(new Edge(2, 3, 7));
        graph[2].add(new Edge(2, 4, 5));
        graph[3].add(new Edge(3, 0, 6));
        graph[3].add(new Edge(3, 1, 8));
        graph[3].add(new Edge(3, 2, 7));
        graph[3].add(new Edge(3, 4, 9));
        graph[4].add(new Edge(4, 2, 5));
        graph[4].add(new Edge(4, 3, 9));
        // 从节点0开始应用普里姆算法，找到最小生成树
        List<Edge> mst = primMST(graph, 0);
        // 打印最小生成树
        System.out.println("Minimum Spanning Tree:");
        for (Edge edge : mst) {
            System.out.println(edge.from + " - " + edge.to + ", weight: " + edge.weight);
        }
    }
    // 边类
    private static class Edge {
        int from;
        int to;
        int weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
}

运行结果：

yaml复制代码Minimum Spanning Tree:
0 - 1, weight: 2
1 - 2, weight: 3
2 - 4, weight: 5
0 - 3, weight: 6

总结：

修路问题是普里姆算法的一个经典应用，通过使用普里姆算法，我们可以找到带权无向图的最小生成树，即通过修建若干条边连接所有节点，并且总权值最小。普里姆算法基于贪心策略，每次选择距离最近的节点，并将其加入最小生成树，直到最小生成树包含所有节点。普里姆算法的时间复杂度取决于边的数量和节点的数量，通常是一个高效的解决方案。在实际应用中，普里姆算法经常用于网络规划、通信网络、城市规划等问题。

6 克鲁斯卡尔算法经典问题：公交站问题

公交站问题是克鲁斯卡尔算法（Kruskal’s Algorithm）的一个经典应用。在公交站问题中，给定一组公交站和它们之间的道路，每条道路都有一个权值（表示两个公交站之间的距离或费用）。目标是找到连接所有公交站的最小总距离或费用的道路网络，即最小生成树。

克鲁斯卡尔算法实现步骤：

将所有道路按照权值从小到大进行排序。
创建一个空的最小生成树。
依次选择排序后的道路，将其加入最小生成树中，要保证加入的道路不会形成环路。
重复步骤3，直到最小生成树包含了所有公交站。

完整代码：

下面给出一个Java实现的公交站问题的代码：

java复制代码import java.util.*;
public class KruskalAlgorithm {
    // 公交站问题的克鲁斯卡尔算法实现
    public static List<Edge> kruskalMST(List<Edge> edges, int numNodes) {
        List<Edge> mst = new ArrayList<>(); // 最小生成树
        Collections.sort(edges, Comparator.comparingInt(e -> e.weight)); // 将道路按照权值从小到大排序
        UnionFind uf = new UnionFind(numNodes); // 使用并查集来判断是否会形成环路
        // 遍历所有道路，将不会形成环路的道路加入最小生成树
        for (Edge edge : edges) {
            if (uf.find(edge.from) != uf.find(edge.to)) {
                mst.add(edge);
                uf.union(edge.from, edge.to);
            }
        }
        return mst;
    }
    public static void main(String[] args) {
        // 创建道路
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 3, 6));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(1, 3, 8));
        edges.add(new Edge(2, 4, 5));
        edges.add(new Edge(3, 4, 9));
        int numNodes = 5; // 公交站数量
        // 找到最小生成树
        List<Edge> mst = kruskalMST(edges, numNodes);
        // 打印最小生成树
        System.out.println("Minimum Spanning Tree:");
        for (Edge edge : mst) {
            System.out.println(edge.from + " - " + edge.to + ", weight: " + edge.weight);
        }
    }
    // 道路类
    private static class Edge {
        int from;
        int to;
        int weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    // 并查集类
    private static class UnionFind {
        int[] parent;
        public UnionFind(int numNodes) {
            parent = new int[numNodes];
            for (int i = 0; i < numNodes; i++) {
                parent[i] = i;
            }
        }
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        }
    }
}

运行结果：

yaml复制代码Minimum Spanning Tree:
0 - 1, weight: 2
1 - 2, weight: 3
2 - 4, weight: 5
0 - 3, weight: 6

总结：

公交站问题是克鲁斯卡尔算法的一个经典应用，通过使用克鲁斯卡尔算法，我们可以找到连接所有公交站的最小总距离或费用的道路网络，即最小生成树。克鲁斯卡尔算法基于贪心策略，每次选择权值最小的道路，并将其加入最小生成树，要保证加入的道路不会形成环路。克鲁斯卡尔算法的时间复杂度取决于边的数量和公交站的数量，通常是一个高效的解决方案。在实际应用中，克鲁斯卡尔算法经常用于网络规划、公共交通规划、电路设计等问题。

7 迪杰斯特拉算法经典问题：最短路径问题

最短路径问题是迪杰斯特拉算法（Dijkstra’s Algorithm）的一个经典应用。在最短路径问题中，给定一个有向图或带权无向图，每条边都有一个非负权值，以及一个起始节点。目标是找到从起始节点到其他所有节点的最短路径，即最小权值的路径。

迪杰斯特拉算法实现步骤：

初始化一个距离数组 dist[]，用于存储从起始节点到其他节点的最短距离。起始节点的距离设置为0，其他节点的距离设置为无穷大。
创建一个优先队列 minHeap，用于按距离从小到大的顺序选择下一个要访问的节点。
将起始节点加入优先队列，并设置距离为0。
重复以下步骤，直到优先队列为空：
a. 从优先队列中选择距离最小的节点。b. 对于该节点的所有邻居节点，计算从起始节点到该邻居节点的距离，如果该距离比当前记录的距离小，则更新距离。c. 将该邻居节点加入优先队列，并更新其距离。

完整代码：

下面给出一个Java实现的最短路径问题的代码：

java复制代码import java.util.*;
public class DijkstraAlgorithm {
    // 最短路径问题的迪杰斯特拉算法实现
    public static int[] dijkstra(int[][] graph, int startNode) {
        int numNodes = graph.length;
        int[] dist = new int[numNodes];
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 创建优先队列，用于按距离从小到大的顺序选择下一个要访问的节点
        PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.dist));
        // 将起始节点加入优先队列，并设置距离为0
        minHeap.offer(new Node(startNode, 0));
        dist[startNode] = 0;
        // 循环直到优先队列为空
        while (!minHeap.isEmpty()) {
            Node currentNode = minHeap.poll();
            int node = currentNode.node;
            // 对于当前节点的所有邻居节点，计算从起始节点到该邻居节点的距离，如果该距离比当前记录的距离小，则更新距离
            for (int neighbor = 0; neighbor < numNodes; neighbor++) {
                if (graph[node][neighbor] != 0 && dist[node] + graph[node][neighbor] < dist[neighbor]) {
                    dist[neighbor] = dist[node] + graph[node][neighbor];
                    minHeap.offer(new Node(neighbor, dist[neighbor]));
                }
            }
        }
        return dist;
    }
    public static void main(String[] args) {
        // 创建带权有向图
        int numNodes = 5;
        int[][] graph = new int[numNodes][numNodes];
        graph[0][1] = 10;
        graph[0][4] = 5;
        graph[1][2] = 1;
        graph[1][4] = 2;
        graph[2][3] = 4;
        graph[3][2] = 6;
        graph[3][0] = 7;
        graph[4][1] = 3;
        graph[4][2] = 9;
        graph[4][3] = 2;
        int startNode = 0; // 起始节点
        // 找到起始节点到其他所有节点的最短路径
        int[] shortestDistances = dijkstra(graph, startNode);
        // 打印最短路径
        System.out.println("Shortest distances from node " + startNode + " to other nodes:");
        for (int i = 0; i < numNodes; i++) {
            System.out.println("Node " + i + ": " + shortestDistances[i]);
        }
    }
    // 节点类，用于存储节点和距离信息
    private static class Node {
        int node;
        int dist;
        public Node(int node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }
}

运行结果：

yaml复制代码Shortest distances from node 0 to other nodes:
Node 0: 0
Node 1: 8
Node 2: 9
Node 3: 7
Node 4: 5

总结：

最短路径问题是迪杰斯特拉算法的一个经典应用，通过使用迪杰斯特拉算法，我们可以找到从起始节点到其他所有节点的最短路径，即最小权值的路径。

8 弗洛伊德算法经典问题：最短路径问题

最短路径问题是弗洛伊德算法（Floyd-Warshall Algorithm）的一个经典应用。在最短路径问题中，给定一个带权有向图或带权无向图，每条边都有一个非负权值。目标是找到任意两个节点之间的最短路径的权值。

弗洛伊德算法实现步骤：

初始化一个二维数组 dist[][]，用于存储任意两个节点之间的最短路径的权值。
将所有的边的权值填入 dist[][]，如果节点i到节点j有直接的边，则 dist[i][j] 的值为该边的权值，否则为无穷大。
通过动态规划的思想，依次遍历所有节点k，并尝试更新 dist[i][j]，使得 dist[i][j] 变为节点i到节点j经过节点k的路径的权值，与直接路径的权值进行比较，取较小值。
重复步骤3，直到所有节点的最短路径权值都计算出来。

完整代码：

下面给出一个Java实现的最短路径问题的代码：

java复制代码import java.util.Arrays;
public class FloydWarshallAlgorithm {
    // 最短路径问题的弗洛伊德算法实现
    public static int[][] floydWarshall(int[][] graph) {
        int numNodes = graph.length;
        int[][] dist = new int[numNodes][numNodes];
        // 初始化dist数组，将边的权值填入数组，如果节点i到节点j没有直接的边，则距离设为无穷大
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else if (graph[i][j] != 0) {
                    dist[i][j] = graph[i][j];
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        // 动态规划求解最短路径
        for (int k = 0; k < numNodes; k++) {
            for (int i = 0; i < numNodes; i++) {
                for (int j = 0; j < numNodes; j++) {
                    // 更新dist[i][j]，使得dist[i][j]变为节点i到节点j经过节点k的路径的权值，与直接路径的权值进行比较，取较小值
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        return dist;
    }
    public static void main(String[] args) {
        // 创建带权有向图
        int numNodes = 5;
        int[][] graph = new int[numNodes][numNodes];
        graph[0][1] = 10;
        graph[0][4] = 5;
        graph[1][2] = 1;
        graph[1][4] = 2;
        graph[2][3] = 4;
        graph[3][2] = 6;
        graph[3][0] = 7;
        graph[4][1] = 3;
        graph[4][2] = 9;
        graph[4][3] = 2;
        // 找到任意两个节点之间的最短路径的权值
        int[][] shortestDistances = floydWarshall(graph);
        // 打印最短路径
        System.out.println("Shortest distances between any two nodes:");
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                System.out.print(shortestDistances[i][j] + " ");
            }
            System.out.println();
        }
    }
}

运行结果：

sql复制代码Shortest distances between any two nodes:
0 8 9 7 5 
10 0 1 3 2 
11 1 0 4 3 
7 5 4 0 2 
12 2 3 5 0

总结：

最短路径问题是弗洛伊德算法的一个经典应用，通过使用弗洛伊德算法，我们可以找到任意两个节点之间的最短路径的权值。弗洛伊德算法使用动态规划的思想，依次遍历所有节点k，并尝试更新节点i到节点j的最短路径权值，使其变为节点i到节点j经过节点k的路径的权值，与直接路径的权值进行比较，取较小值。弗洛伊德算法适用于带权有向图或带权无向图，其中边的权值可以为任意非负值。弗洛伊德算法的时间复杂度为O(n^3)，其中n是节点的数量，因此在较大规模的图中也可以得到较好的运行效率。在实际应用中，弗洛伊德算法经常用于计算网络中的最短路径，路由选择等问题。

数据结构与算法：8种算法经典问题

前言

数据结构与算法文章列表

目录

1 分治算法经典问题：汉诺塔问题

2 动态规划算法经典问题：背包问题

2.1 0-1背包问题

2.2 完全背包问题

2.3 多重背包问题

3 KMP算法经典问题：字符串匹配问题

4 贪心算法经典问题：集合覆盖问题

5 普里姆算法经典问题：修路问题

6 克鲁斯卡尔算法经典问题：公交站问题

7 迪杰斯特拉算法经典问题：最短路径问题

8 弗洛伊德算法经典问题：最短路径问题

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构与算法：8种算法经典问题

前言

数据结构与算法文章列表

目录

1 分治算法经典问题：汉诺塔问题

2 动态规划算法经典问题：背包问题

2.1 0-1背包问题

2.2 完全背包问题

2.3 多重背包问题

3 KMP算法经典问题：字符串匹配问题

4 贪心算法经典问题：集合覆盖问题

5 普里姆算法经典问题：修路问题

6 克鲁斯卡尔算法经典问题：公交站问题

7 迪杰斯特拉算法经典问题：最短路径问题

8 弗洛伊德算法经典问题：最短路径问题

热门文章

最新文章

相关课程

相关电子书

相关实验场景