蓝桥杯 Java B 组之最短路径算法（Dijkstra、Floyd-Warshall）

Day 2：最短路径算法（Dijkstra、Floyd-Warshall）

📖 一、最短路径算法简介

最短路径问题是图论中的经典问题，主要用于求解 单源最短路径 或 多源最短路径。在实际应用中，最短路径广泛应用于 导航系统、网络路由、任务调度 等场景。

📌 最短路径算法分类

算法	适用场景	时间复杂度
Dijkstra	单源最短路径（无负权）	O((V+E) logV)（使用优先队列优化）
Floyd-Warshall	多源最短路径	O(V³)
Bellman-Ford	处理负权边的单源最短路径	O(VE)

📖 二、Dijkstra 算法（单源最短路径）

适用范围：

适用于无负权边的单源最短路径问题。
主要思想是：使用 贪心 + 优先队列 找到当前最短的路径。

🔹 1. 题目：网络延迟时间（Leetcode 743）

题目描述：给定 n 个节点的有向图，边 times[i] = (u, v, w) 表示从 u 到 v 的边权为 w。从源点 k 发送信号，计算所有节点都收到信号的最短时间，若无法到达所有节点，返回 -1。

示例

输入: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出: 2

🔹 2. 思路

使用 Dijkstra 算法，**优先队列（最小堆）**优化时间复杂度。
维护 dist[] 数组，dist[i] 代表从 k 到 i 的最短路径。
使用 最小堆（PriorityQueue） 维护当前最短路径的节点，每次弹出最短路径节点，更新其邻接点。

🔹 3. 代码实现

import java.util.*;public class DijkstraNetworkDelay {public int networkDelayTime(int[][] times, int n, int k) {// 图的邻接表Map<Integer, List<int[]>> graph = new HashMap<>();for (int[] edge : times) {graph.putIfAbsent(edge[0], new ArrayList<>());graph.get(edge[0]).add(new int[]{edge[1], edge[2]});}// 最小堆（按路径权值排序）PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));pq.offer(new int[]{k, 0}); // 从源点 k 开始Map<Integer, Integer> dist = new HashMap<>();while (!pq.isEmpty()) {int[] cur = pq.poll();int node = cur[0], time = cur[1];if (dist.containsKey(node)) continue; // 已访问dist.put(node, time);if (!graph.containsKey(node)) continue;for (int[] next : graph.get(node)) {int neighbor = next[0], weight = next[1];if (!dist.containsKey(neighbor)) {pq.offer(new int[]{neighbor, time + weight});}}}if (dist.size() < n) return -1; // 说明有节点不可达return Collections.max(dist.values()); // 返回最长的最短路径}public static void main(String[] args) {DijkstraNetworkDelay solution = new DijkstraNetworkDelay();int[][] times = {{2,1,1},{2,3,1},{3,4,1}};int n = 4, k = 2;System.out.println(solution.networkDelayTime(times, n, k)); // 输出 2}
}

🔹 4. 代码讲解

构建邻接表：用 Map<Integer, List<int[]>> 存储 邻接节点和权重。
使用优先队列（最小堆）：每次取出当前路径最短的节点进行扩展，更新邻接点的最短路径。
利用 dist[] 数组：记录从 k 到各个节点的最短路径。
时间复杂度：
- O((V+E) logV)（优先队列优化）。
- 其中 V 是顶点数，E 是边数。

📖 三、Floyd-Warshall 算法（多源最短路径）

适用范围：

适用于多源最短路径问题。
允许 负权边（但不能有负权环）。
主要思想是：动态规划，每次考虑是否经过某个中间点 k 能让路径更短。

🔹 1. 题目：2019 省赛 - 迷宫

题目描述：给定一个 n × n 的迷宫，1 表示墙，0 表示可通行。求从起点 (0,0) 到终点 (n-1,n-1) 的最短路径。

输入示例

输出

（路径 [(0,0) -> (1,1) -> (2,1) -> (2,2) -> (2,3) -> (3,3)]）

🔹 2. 思路

转换为图问题：迷宫是一个 n × n 的无向图，连通区域是 可通行的 0。
使用 Floyd-Warshall 算法：
- 令 dist[i][j] 存储 从 (0,0) 到 (i,j) 的最短路径。
- 若 grid[i][j] == 1，设 dist[i][j] = ∞（墙）。
- 令 dist[i][j] = min(dist[i][j], dist[k][m] + 1)，其中 (k,m) 是邻居。

🔹 3. 代码实现

import java.util.*;public class FloydWarshallMaze {static final int INF = 10000; // 设定一个较大的数表示不可达static int[][] dist;static int[][] directions = {{1,0}, {0,1}, {-1,0}, {0,-1}}; // 上下左右四个方向public static int shortestPath(int[][] maze) {int n = maze.length;dist = new int[n][n];// 初始化距离数组for (int i = 0; i < n; i++) {Arrays.fill(dist[i], INF);}dist[0][0] = 0; // 起点// Floyd-Warshall 核心算法for (int k = 0; k < n; k++) { // 中间点for (int i = 0; i < n; i++) { // 起点for (int j = 0; j < n; j++) { // 终点if (maze[i][j] == 0) {for (int[] dir : directions) {int x = i + dir[0], y = j + dir[1];if (x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 0) {dist[x][y] = Math.min(dist[x][y], dist[i][j] + 1);}}}}}}return dist[n-1][n-1] == INF ? -1 : dist[n-1][n-1];}public static void main(String[] args) {int[][] maze = {{0, 0, 1, 0},{1, 0, 1, 0},{1, 0, 0, 0},{1, 1, 1, 0}};System.out.println(shortestPath(maze)); // 输出 5}
}