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

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

📖 一、最短路径算法简介

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

📌 最短路径算法分类

📖 二、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. 代码讲解

1. 构建邻接表：用 Map<Integer, List<int[]>> 存储 邻接节点和权重。
2. 使用优先队列（最小堆）：每次取出当前路径最短的节点进行扩展，更新邻接点的最短路径。
3. 利用 dist[] 数组：记录从 k 到各个节点的最短路径。
4. 时间复杂度：
   • 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. 思路

1. 转换为图问题：迷宫是一个 n × n 的无向图，连通区域是 可通行的 0。
2. 使用 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 + 优先队列优化（最小堆 PriorityQueue）。
• 理解 Floyd-Warshall 多源最短路径的动态规划思想。