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

爱被打了一巴掌 2023-10-13 21:43 29阅读 0赞

## 前言 ##

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

--------------------

#### 数据结构与算法文章列表 ####

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

--------------------

## 目录 ##

![8种算法经典问题.png][8_.png]

--------------------

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

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

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

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

**实现步骤**：

1.  定义一个递归函数，该函数接受以下参数：
    
     *  `n`：要移动的圆盘数量。
     *  `source`：表示初始柱子。
     *  `target`：表示目标柱子。
     *  `auxiliary`：表示辅助柱子。
2.  在函数内部，通过递归进行以下步骤：  
    a. 如果 `n == 1`，直接将圆盘从 `source` 移动到 `target`。  
    b. 否则，先将 `n-1` 个圆盘从 `source` 经由 `target` 移动到 `auxiliary`。  
    c. 然后将第 `n` 个圆盘从 `source` 移动到 `target`。  
    d. 最后，将 `n-1` 个圆盘从 `auxiliary` 经由 `source` 移动到 `target`。
3.  调用递归函数，将所有圆盘从柱子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`。要求在不超过背包容量的情况下，选择物品使得总价值最大，且每个物品只能选择一次放入背包。

实现步骤：

1.  定义动态规划数组：创建一个`dp`二维数组，其中`dp[i][j]`表示在前`i`个物品中选择，且背包容量为`j`时的最大总价值。
2.  初始化：将`dp[i][0]`和`dp[0][j]`都初始化为0，表示背包容量为0或没有物品可选时，获得的最大总价值为0。
3.  状态转移方程：遍历每个物品，更新`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`。要求在不超过背包容量的情况下，选择物品使得总价值最大，且每个物品可以选择无限次放入背包。

实现步骤：

1.  定义动态规划数组：创建一个`dp`数组，其中`dp[i]`表示背包容量为`i`时，可以获得的最大总价值。
2.  初始化：将`dp[0]`初始化为0，表示背包容量为0时，获得的最大总价值为0。
3.  状态转移方程：遍历每个物品，更新`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`次。

实现步骤：

1.  定义动态规划数组：创建一个`dp`二维数组，其中`dp[i][j]`表示在前`i`个物品中选择，且背包容量为`j`时的最大总价值。
2.  初始化：将`dp[i][0]`和`dp[0][j]`都初始化为0，表示背包容量为0或没有物品可选时，获得的最大总价值为0。
3.  状态转移方程：遍历每个物品，对于每个物品，我们需要考虑选择`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算法的实现步骤**：

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

**KMP算法的详细步骤**：

1.  根据子串构建部分匹配表。
2.  初始化两个指针：`i`指向主串，`j`指向子串。
3.  从头开始遍历主串和子串：  
    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 贪心算法经典问题：集合覆盖问题 ###

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

**贪心算法实现步骤**：

1.  初始化一个空的集合 `selectedSet`，用于存储所选的子集合。
2.  从剩余未覆盖元素的全集中，选择一个能覆盖最多未覆盖元素的子集合，并将其加入 `selectedSet`。
3.  重复步骤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），即通过修建若干条边连接所有节点，并且总权值最小。

**普里姆算法实现步骤**：

1.  选择一个起始节点，将其加入最小生成树。
2.  重复以下步骤，直到最小生成树包含了所有节点：  
    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）的一个经典应用。在公交站问题中，给定一组公交站和它们之间的道路，每条道路都有一个权值（表示两个公交站之间的距离或费用）。目标是找到连接所有公交站的最小总距离或费用的道路网络，即最小生成树。

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

1.  将所有道路按照权值从小到大进行排序。
2.  创建一个空的最小生成树。
3.  依次选择排序后的道路，将其加入最小生成树中，要保证加入的道路不会形成环路。
4.  重复步骤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）的一个经典应用。在最短路径问题中，给定一个有向图或带权无向图，每条边都有一个非负权值，以及一个起始节点。目标是找到从起始节点到其他所有节点的最短路径，即最小权值的路径。

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

1.  初始化一个距离数组 `dist[]`，用于存储从起始节点到其他节点的最短距离。起始节点的距离设置为0，其他节点的距离设置为无穷大。
2.  创建一个优先队列 `minHeap`，用于按距离从小到大的顺序选择下一个要访问的节点。
3.  将起始节点加入优先队列，并设置距离为0。
4.  重复以下步骤，直到优先队列为空：  
    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）的一个经典应用。在最短路径问题中，给定一个带权有向图或带权无向图，每条边都有一个非负权值。目标是找到任意两个节点之间的最短路径的权值。

**弗洛伊德算法实现步骤**：

1.  初始化一个二维数组 `dist[][]`，用于存储任意两个节点之间的最短路径的权值。
2.  将所有的边的权值填入 `dist[][]`，如果节点i到节点j有直接的边，则 `dist[i][j]` 的值为该边的权值，否则为无穷大。
3.  通过动态规划的思想，依次遍历所有节点k，并尝试更新 `dist[i][j]`，使得 `dist[i][j]` 变为节点i到节点j经过节点k的路径的权值，与直接路径的权值进行比较，取较小值。
4.  重复步骤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是节点的数量，因此在较大规模的图中也可以得到较好的运行效率。在实际应用中，弗洛伊德算法经常用于计算网络中的最短路径，路由选择等问题。

[Link 1]: https://juejin.cn/post/7067947470688354311
[8_.png]: https://img-blog.csdnimg.cn/img_convert/1d471fddfa01fbbfc0aae4aa5294e68c.webp?x-oss-process=image/format,png