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) 的最短路径。
输入示例
4
0 0 1 0
1 0 1 0
1 0 0 0
1 1 1 0
输出
5
（路径 [(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
}
}
📖 四、总结
Dijkstra vs Floyd-Warshall
| 算法 | 适用范围 | 时间复杂度 |
|---|---|---|
| Dijkstra | 单源最短路径 | O((V+E) logV) |
| Floyd-Warshall | 多源最短路径 | O(V³) |
🎯 练习建议
- 熟练掌握 Dijkstra + 优先队列优化（最小堆
PriorityQueue）。 - 理解 Floyd-Warshall 多源最短路径的动态规划思想。
