📝 写在前面

在地图导航、网络路由、任务规划等场景中，最短路径问题无处不在。给定一个图（有向/无向），找到从一个顶点到另一个顶点的最短路径（权值和最小）。今天我们来学习四种经典的最短路径算法，它们各有千秋：

算法 类型 适用场景 时间复杂度 特点
Dijkstra 单源 非负权图 O((V+E)logV) 贪心，效率高
Bellman-Ford 单源 可含负权，检测负环 O(VE) 容忍负权，可检测负环
Floyd-Warshall 多源 任意两点 O(V³) 动态规划，简洁
SPFA 单源 稀疏图，负权 平均O(kE)，最坏O(VE) 队列优化Bellman-Ford

阅读指南：每个算法包含👇

  • 一句话记住核心思想

  • 算法可视化：mermaid流程图

  • 代码实现：带详细注释

  • LeetCode实战：典型例题+解题代码

一、Dijkstra算法 —— 贪心者的最短路径

🎯 一句话记住

每次选个离起点最近的点，用它去更新邻居，就像水滴扩散。

🤔 核心思想

Dijkstra算法适用于所有边权非负的图。它维护一个距离数组 dist，表示从起点到各个顶点的当前最短距离。每次从未确定的顶点中选出 dist 最小的顶点（贪心选择），然后用它去松弛它的邻居。重复V次。

优化：使用优先队列（最小堆）来快速选取最小距离顶点，复杂度 O((V+E)logV)。

📊 Dijkstra流程图

💻 代码实现（邻接表+优先队列）

/**
 * Dijkstra算法求单源最短路径
 * @param {number} n 顶点数（顶点编号0~n-1）
 * @param {number[][]} edges 边集 [u, v, w]
 * @param {number} start 起点
 * @returns {number[]} 从start到各点的最短距离，不可达为Infinity
 */
function dijkstra(n, edges, start) {
    // 构建邻接表
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v, w] of edges) {
        graph[u].push({ to: v, weight: w });
        // 如果无向图，还需添加反向边：graph[v].push({to: u, weight: w});
    }
    
    const dist = new Array(n).fill(Infinity);
    dist[start] = 0;
    
    // 最小堆，按距离排序
    const pq = new MinPriorityQueue({ priority: (item) => item.dist });
    pq.enqueue({ node: start, dist: 0 });
    
    const visited = new Array(n).fill(false);
    
    while (!pq.isEmpty()) {
        const { node: u } = pq.dequeue();
        if (visited[u]) continue;
        visited[u] = true;
        
        for (const { to: v, weight } of graph[u]) {
            const newDist = dist[u] + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.enqueue({ node: v, dist: newDist });
            }
        }
    }
    
    return dist;
}

// 注意：MinPriorityQueue 是LeetCode环境内置的，实际可用堆实现或使用第三方库

🏆 LeetCode实战：网络延迟时间

题目：LeetCode 743. 网络延迟时间

题目描述：有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间。times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 k 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

思路分析：
从节点 k 出发，求到所有节点的最短路径中的最大值。如果存在不可达节点，返回 -1。直接套用 Dijkstra 算法。

解题代码：

/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function(times, n, k) {
    // 构建邻接表
    const graph = Array.from({ length: n + 1 }, () => []); // 节点编号1~n
    for (const [u, v, w] of times) {
        graph[u].push({ to: v, weight: w });
    }
    
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    
    // 使用优先队列（最小堆）
    const pq = new MinPriorityQueue({ priority: (item) => item.dist });
    pq.enqueue({ node: k, dist: 0 });
    
    while (!pq.isEmpty()) {
        const { node: u } = pq.dequeue().element;
        // 因为优先队列可能包含同一个节点的多个条目，需要跳过已处理的
        // 这里我们可以不设 visited，但需要判断如果出队的距离大于当前记录的距离，说明是旧数据，跳过
        if (dist[u] < pq.front()?.priority) continue; // 简化处理，实际建议用visited
        
        for (const { to: v, weight } of graph[u]) {
            const newDist = dist[u] + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.enqueue({ node: v, dist: newDist });
            }
        }
    }
    
    // 找最大值
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }
    return maxDist;
};

时间复杂度：O((V+E)logV)
空间复杂度：O(V+E)

二、Bellman-Ford算法 —— 负权路上的行者

🎯 一句话记住

反复松弛所有边，做 V-1 轮，就能找到最短路径，还能揪出负环。

🤔 核心思想

Bellman-Ford 算法可以处理负权边，并且能检测负权环（环上权值和为负）。它进行 V-1 轮松弛操作（每轮对所有边进行松弛），因为最短路径最多包含 V-1 条边。如果第 V 轮还能松弛，说明存在负环。

松弛操作：对于边 (u, v, w)，如果 dist[u] + w < dist[v]，则更新 dist[v] = dist[u] + w。

💻 代码实现

/**
 * Bellman-Ford算法求单源最短路径，可检测负环
 * @param {number} n 顶点数
 * @param {number[][]} edges 边集 [u, v, w]
 * @param {number} start 起点
 * @returns {number[]|null} 最短距离数组，若存在负环则返回null
 */
function bellmanFord(n, edges, start) {
    const dist = new Array(n).fill(Infinity);
    dist[start] = 0;
    
    // 进行 V-1 轮松弛
    for (let i = 0; i < n - 1; i++) {
        let updated = false;
        for (const [u, v, w] of edges) {
            if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break; // 提前结束
    }
    
    // 第V轮检测负环
    for (const [u, v, w] of edges) {
        if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
            return null; // 存在负环
        }
    }
    
    return dist;
}

🏆 LeetCode实战：K站中转内最便宜的航班

题目：LeetCode 787. K站中转内最便宜的航班

题目描述：有 n 个城市通过一些航班连接。给你一个数组 flights，其中 flights[i] = [from_i, to_i, price_i] ，表示该航班都从城市 from_i 开始，以价格 price_i 抵达 to_i。现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。如果不存在这样的路线，则输出 -1。

思路分析：
这题是 Bellman-Ford 的变种，限制最多经过 k 条边（即 k+1 段航班）。我们可以做 k+1 轮松弛，但要注意每轮只能基于上一轮的结果，避免同一轮内串联更新（即使用上一轮的 dist 副本）。通常用动态规划也可以，但 Bellman-Ford 思想很适合。

解题代码：

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
var findCheapestPrice = function(n, flights, src, dst, k) {
    let dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    
    // 最多 k+1 轮（因为 k 次中转，即 k+1 条边）
    for (let i = 0; i <= k; i++) {
        const newDist = [...dist]; // 使用副本，防止本轮内串联
        for (const [u, v, price] of flights) {
            if (dist[u] !== Infinity && dist[u] + price < newDist[v]) {
                newDist[v] = dist[u] + price;
            }
        }
        dist = newDist;
    }
    
    return dist[dst] === Infinity ? -1 : dist[dst];
};

时间复杂度：O(k × E)
空间复杂度：O(n)

三、Floyd-Warshall算法 —— 多源最短路径的万能钥匙

🎯 一句话记住

三重循环，动态规划，任意两点之间的最短路径，一网打尽。

🤔 核心思想

Floyd-Warshall 算法用于求所有点对的最短路径。它基于动态规划：dp[k][i][j] 表示经过前 k 个顶点（0..k-1）作为中间点时，i 到 j 的最短路径长度。状态转移：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])。空间优化后可以用二维数组，三重循环 k, i, j。

注意：算法要求图中无负环（但可以有负权边，只要没有负环即可正确求出最短路径，如果有负环则算法可能产生错误结果）。

💻 代码实现

/**
 * Floyd-Warshall算法求所有点对最短路径
 * @param {number} n 顶点数
 * @param {number[][]} edges 边集 [u, v, w]（可能有负权，但无负环）
 * @returns {number[][]} 距离矩阵，若不可达则为Infinity
 */
function floydWarshall(n, edges) {
    // 初始化距离矩阵
    const dist = Array.from({ length: n }, () => new Array(n).fill(Infinity));
    for (let i = 0; i < n; i++) dist[i][i] = 0;
    for (const [u, v, w] of edges) {
        dist[u][v] = Math.min(dist[u][v], w); // 处理重边
        // 如果是无向图，还需 dist[v][u] = w;
    }
    
    // 三重循环
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            if (dist[i][k] === Infinity) continue; // 剪枝
            for (let j = 0; j < n; j++) {
                if (dist[k][j] === Infinity) continue;
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    return dist;
}

🏆 LeetCode实战：阈值距离内邻居最少的城市

题目：LeetCode 1334. 阈值距离内邻居最少的城市

题目描述：有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [from_i, to_i, weight_i] 代表 from_i 和 to_i 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

思路分析：
需要求出所有点对之间的最短路径，然后统计每个城市在阈值内可达的城市数量。Floyd-Warshall 正好适合。

解题代码：

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} distanceThreshold
 * @return {number}
 */
var findTheCity = function(n, edges, distanceThreshold) {
    // Floyd-Warshall
    const INF = 1e9;
    const dist = Array.from({ length: n }, () => new Array(n).fill(INF));
    for (let i = 0; i < n; i++) dist[i][i] = 0;
    for (const [u, v, w] of edges) {
        dist[u][v] = Math.min(dist[u][v], w);
        dist[v][u] = Math.min(dist[v][u], w);
    }
    
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // 统计每个城市在阈值内可达的城市数
    let minCount = n;
    let result = -1;
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (i !== j && dist[i][j] <= distanceThreshold) {
                count++;
            }
        }
        if (count < minCount || (count === minCount && i > result)) {
            minCount = count;
            result = i;
        }
    }
    
    return result;
};

时间复杂度：O(n³)
空间复杂度：O(n²)

四、SPFA算法 —— 队列优化的Bellman-Ford

🎯 一句话记住

只有上一轮被更新的点才可能引起下一轮更新，用队列记下它们。

🤔 核心思想

SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的队列优化版本。它维护一个队列，初始时将起点入队。每次取出队首顶点 u，尝试松弛它的所有邻接边；如果某个邻接点 v 的距离被更新且 v 不在队列中，就将 v 入队。重复直到队列为空。

优点：在稀疏图上通常很快，平均复杂度 O(kE)，k 为常数。
缺点：最坏情况可能退化为 O(VE)，且可能被某些数据卡死。

负环检测：如果一个顶点入队次数超过 V 次，说明存在负环。

💻 代码实现

/**
 * SPFA算法求单源最短路径，可检测负环
 * @param {number} n 顶点数
 * @param {number[][]} edges 边集 [u, v, w]
 * @param {number} start 起点
 * @returns {number[]|null} 最短距离数组，若存在负环则返回null
 */
function spfa(n, edges, start) {
    // 构建邻接表
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v, w] of edges) {
        graph[u].push({ to: v, weight: w });
    }
    
    const dist = new Array(n).fill(Infinity);
    dist[start] = 0;
    
    const queue = [start];
    const inQueue = new Array(n).fill(false);
    inQueue[start] = true;
    const count = new Array(n).fill(0); // 记录入队次数
    
    while (queue.length) {
        const u = queue.shift();
        inQueue[u] = false;
        
        for (const { to: v, weight } of graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if (!inQueue[v]) {
                    queue.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    if (count[v] > n) { // 存在负环
                        return null;
                    }
                }
            }
        }
    }
    
    return dist;
}

🏆 LeetCode实战：判断是否存在负环

SPFA 适用于带负权的最短路径问题，比如下面这道题：

题目：给定一个有向图，包含 n 个节点，边可能带有负权。请判断图中是否存在负权环。

思路：使用 SPFA，如果某个节点入队次数超过 n 次，则存在负环。

解题代码（SPFA 版 LeetCode 787）：

var findCheapestPrice = function(n, flights, src, dst, k) {
    // 构建邻接表
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v, p] of flights) {
        graph[u].push({ to: v, price: p });
    }
    
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    const steps = new Array(n).fill(0); // 记录到达每个节点经过的边数（不是必须）
    
};

五、四大算法对比总结

算法 适用场景 时间复杂度 能否处理负权 能否检测负环 特点
Dijkstra 非负权图 O((V+E)logV) ❌ ❌ 贪心，效率高
Bellman-Ford 一般图（可负权） O(VE) ✅ ✅ 原理简单，较慢
Floyd-Warshall 多源最短路（无负环） O(V³) ✅（无负环） ❌ 简洁，适合小图
SPFA 稀疏图（可负权） 平均O(kE)，最坏O(VE) ✅ ✅ 队列优化，不稳定

如何选择？

  • 单源、非负权 → Dijkstra（最快）

  • 单源、可能有负权 → Bellman-Ford（可靠）或 SPFA（快速，但小心被卡）

  • 多源、图较小 → Floyd-Warshall（代码简单）

  • 需要检测负环 → Bellman-Ford 或 SPFA

📌 面试常见问题

  1. Dijkstra 为什么不能处理负权边？

    • Dijkstra 基于贪心，每次选择当前距离最小的点，认为它不会再被更新。但负权边可能导致后面出现更短路径，破坏贪心选择性质。

  2. Bellman-Ford 如何检测负环？

    • 进行 V-1 轮松弛后，再对所有边松弛一次，如果还能更新，说明存在负环。

  3. Floyd-Warshall 的状态转移方程怎么理解？

    • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])，表示考虑经过顶点 k 的路径是否更短。

  4. SPFA 为什么可能被卡？

    • 在某些构造的图中，SPFA 可能退化为 Bellman-Ford 的 O(VE)，如网格图。竞赛中常用 Dijkstra 或 Bellman-Ford 保证稳定性。

🎯 下期预告

下一期我们将进入图论算法（三）：最小生成树——Prim 和 Kruskal，用最少的边连通所有顶点！

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、转发！有问题欢迎在评论区讨论～

# 图论 # 算法 # java
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

SenseVoicecpp sense-voice识别语音[AI人工智能(六十八)]—东方仙盟

avatar AtomGit开源社区
cover

学生成绩分析和弱项辅助系统信息管理系统源码-SpringBoot后端+Vue前端+MySQL【可直接运行】

avatar AtomGit开源社区
cover

Java Web 学生信息管理系统系统源码-SpringBoot2+Vue3+MyBatis-Plus+MySQL8.0【含文档】

avatar AtomGit开源社区