一、最短路径问题：从地图导航到网络路由

最短路径，说白了就是「怎么走最近」。你打开高德地图查路线，后台跑的就是这类算法。我在做分布式系统时，经常要计算节点间的最小延迟路径——嗯，那时候我才真正体会到，选对算法比写对代码重要得多。

今天咱们聊三个最经典的：Dijkstra、Bellman-Ford、Floyd-Warshall。它们各有脾气，适用场景完全不同。

二、Dijkstra：最常用的单源最短路径

Dijkstra 是我个人用得最多的算法。它像个贪心的导游——每次都选当前最近的点，然后更新邻居。前提是：所有边的权重不能为负。

2.1 算法思想

维护一个距离数组 dist[]，初始时 dist[起点]=0，其他为无穷大。每次从「未访问」的节点中挑一个距离最小的，用它去松弛邻居。重复直到所有节点都访问过。

2.2 代码模板

// Dijkstra 标准模板（邻接表 + 优先队列）
public int[] dijkstra(int n, List<int[]>[] graph, int start) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    // 最小堆：[距离, 节点]
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, start});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];

        // 重要：跳过过时记录
        if (d > dist[u]) continue;

        for (int[] edge : graph[u]) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

三、Bellman-Ford：能处理负权边的硬汉

Bellman-Ford 的思路更暴力——我不管顺序，我就对所有边做 V-1 轮松弛。为什么是 V-1？因为最短路径最多包含 V-1 条边，再多就有环了。

3.1 算法思想

说白了就是「暴力松弛」。每一轮遍历所有边，尝试更新距离。做完 V-1 轮后，再跑一轮——如果还能更新，说明存在负权环。

3.2 代码模板

// Bellman-Ford 标准模板
public int[] bellmanFord(int n, int[][] edges, int start) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    // 做 V-1 轮松弛
    for (int i = 0; i < n - 1; i++) {
        boolean updated = false;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        // 优化：如果某轮没更新，提前结束
        if (!updated) break;
    }

    // 检测负权环
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
            // 存在负权环
            return new int[]{-1};
        }
    }
    return dist;
}

四、Floyd-Warshall：全源最短路径的终极方案

Floyd-Warshall 的思路很优雅——我逐个考虑每个节点作为「中间点」，看看能不能让路径更短。你想想看，这其实是个三维的动态规划，只不过压缩成了二维数组。

4.1 算法思想

定义 dp[k][i][j] 表示「只允许使用前 k 个节点作为中间点时，i 到 j 的最短距离」。状态转移：要么不走 k，要么走 k。压缩后就是：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

4.2 代码模板

// Floyd-Warshall 标准模板
public int[][] floydWarshall(int n, int[][] edges) {
    // 初始化距离矩阵
    int[][] dist = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], Integer.MAX_VALUE / 2);
        dist[i][i] = 0;
    }
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        dist[u][v] = Math.min(dist[u][v], w);  // 处理重边
    }

    // 核心三重循环
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    return dist;
}

五、经典例题：网络延迟时间

这道题是 LeetCode 743，也是我当年面试字节时遇到的原题。题目说：有 N 个网络节点，给你一个信号从 K 出发，问所有节点都收到信号需要多久？

说白了就是求 K 到所有节点的最短路径中的最大值。用 Dijkstra 最合适——因为网络延迟不可能是负数。

5.1 解题思路

1. 建图：邻接表，每个节点存 [邻居, 延迟]
2. 跑 Dijkstra，得到 dist[] 数组
3. 取 dist[] 中的最大值——如果还有无穷大，说明有节点不可达，返回 -1

5.2 代码实现

public int networkDelayTime(int[][] times, int n, int k) {
    // 1. 建图
    List<int[]>[] graph = new ArrayList[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    for (int[] t : times) {
        int u = t[0] - 1, v = t[1] - 1, w = t[2];
        graph[u].add(new int[]{v, w});
    }

    // 2. Dijkstra
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k - 1] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, k - 1});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;

        for (int[] edge : graph[u]) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }

    // 3. 取最大值
    int maxDelay = 0;
    for (int d : dist) {
        if (d == Integer.MAX_VALUE) return -1;
        maxDelay = Math.max(maxDelay, d);
    }
    return maxDelay;
}

六、三种算法怎么选？

场景	推荐算法	原因
单源 + 非负权	Dijkstra	最快，O((V+E)logV)
单源 + 可能有负权	Bellman-Ford	能检测负环，但慢
全源 + 稠密图	Floyd-Warshall	代码简单，O(V³) 可接受
全源 + 稀疏图	跑 V 次 Dijkstra	比 Floyd 快

嗯，到这里三种最短路径算法就聊完了。我个人建议：先把 Dijkstra 练熟，它是最常用的。Bellman-Ford 和 Floyd 理解思想就好，面试时能写出来就行。