Dijkstra 算法是解决单源最短路径问题的经典算法。

算法概念

Dijkstra 算法用于在一个加权有向图或无向图中，找到从一个特定源节点到图中所有其他节点的最短路径。

主要特点：

• 单源最短路径：计算从一个固定起点到其他所有点的距离。
• 贪心策略：每次选择当前距离起点最近且未访问过的节点进行扩展。
• 权重限制：不能处理带有负权边的图（如果存在负权边，请使用 Bellman-Ford 或 SPFA 算法）。
• 时间复杂度：
  • 基础版： $O(V^2)$ ，适合稠密图。
  • 堆优化版： $O(E \log V)$ ，适合稀疏图（ $E$ 是边数， $V$ 是顶点数）。

核心思路

Dijkstra 算法的核心在于不断“松弛”（Relaxation）边。

• 初始化：
  • 起点到自身的距离为 0，到其他所有点的距离设为 $\infty$。
  • 使用一个集合 visited 记录已确定最短路径的节点。
• 贪心选择：
  • 从未访问的节点中，选出当前距离起点最近的一个节点 $u$。
• 松弛操作：
  • 遍历节点 $u$ 的所有邻居 $v$。
  • 如果 起点 -> u -> v 的路径长度比当前记录的 起点 -> v 更短，则更新 dist[v]。
• 重复：
  • 重复步骤 2 和 3，直到所有节点都被访问或不再有可优化的路径。

代码实现

• 基础版（适合小规模图）

  /**
   * Dijkstra 基础实现 (邻接矩阵)
   * @param {number[][]} graph - 邻接矩阵
   * @param {number} start - 起点编号
   * @returns {number[]} - 起点到各点的最短距离数组
   */
  function dijkstra(graph, start) {
      const n = graph.length
      const dist = Array(n).fill(Infinity)
      const visited = Array(n).fill(false)
  
      dist[start] = 0
  
      for (let i = 0; i < n; i++) {
          // 1. 找到未访问节点中距离最小的
          let u = -1
          for (let j = 0; j < n; j++) {
              if (!visited[j] && (u === -1 || dist[j] < dist[u])) {
                  u = j
              }
          }
  
          if (dist[u] === Infinity) break
          visited[u] = true
  
          // 2. 松弛邻居节点
          for (let v = 0; j < n; v++) {
              if (!visited[v] && graph[u][v] !== Infinity) {
                  if (dist[u] + graph[u][v] < dist[v]) {
                      dist[v] = dist[u] + graph[u][v]
                  }
              }
          }
      }
      return dist
  }
  

• 堆优化版（适合稀疏图）

  class MinHeap {
      constructor() {
          this.heap = []
      }
      push(val) {
          this.heap.push(val)
          this.bubbleUp()
      }
      pop() {
          if (this.size() === 0) return null
          if (this.size() === 1) return this.heap.pop()
          const top = this.heap[0]
          this.heap[0] = this.heap.pop()
          this.bubbleDown()
          return top
      }
      size() {
          return this.heap.length
      }
      bubbleUp() {
          let index = this.heap.length - 1
          while (index > 0) {
              let pIdx = Math.floor((index - 1) / 2)
              if (this.heap[index][0] >= this.heap[pIdx][0]) break
              ;[this.heap[index], this.heap[pIdx]] = [this.heap[pIdx], this.heap[index]]
              index = pIdx
          }
      }
      bubbleDown() {
          let index = 0
          while (true) {
              let L = 2 * index + 1,
                  R = 2 * index + 2,
                  swap = null
              if (L < this.heap.length && this.heap[L][0] < this.heap[index][0]) swap = L
              if (
                  R < this.heap.length &&
                  (swap === null ? this.heap[R][0] < this.heap[index][0] : this.heap[R][0] < this.heap[L][0])
              )
                  swap = R
              if (swap === null) break
              ;[this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]]
              index = swap
          }
      }
  }
  
  /**
   * 堆优化的 Dijkstra 算法
   * @param {number} n - 节点数量
   * @param {Map} adj - 邻接表
   * @param {number} start - 起点
   * @returns {number[]} - 距离数组
   */
  function dijkstraOptimized(n, adj, start) {
      const dist = new Array(n).fill(Infinity)
      dist[start] = 0
      const pq = new MinHeap()
      pq.push([0, start]) // [距离, 节点]
  
      while (pq.size() > 0) {
          const [d, u] = pq.pop()
          if (d > dist[u]) continue // 关键优化：跳过过时路径
  
          const neighbors = adj.get(u) || []
          for (const [v, weight] of neighbors) {
              if (dist[u] + weight < dist[v]) {
                  dist[v] = dist[u] + weight
                  pq.push([dist[v], v])
              }
          }
      }
      return dist
  }
  

LeetCode 题目案例

• 743. 网络延迟时间

题目描述： 有 $n$ 个网络节点，标记为 $1$ 到 $n$。给你一个列表 times，表示信号经过有向边的传递时间。现在，我们从某个节点 $k$ 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 $-1$。

解析： 这道题要求计算从起点 $k$ 到达所有节点的最长“最短路径”。

JS 实现（堆优化版）： 在 JavaScript 中，由于没有原生的优先队列，通常需要手动实现一个简易的最小堆来达到 $O(E \log V)$ 的复杂度。

var networkDelayTime = function (times, n, k) {
    // 1. 构建邻接表
    const adj = Array.from({ length: n + 1 }, () => [])
    for (const [u, v, w] of times) {
        adj[u].push([v, w])
    }

    const dist = Array(n + 1).fill(Infinity)
    dist[k] = 0

    // 2. 优先队列 (最小堆存储: [distance, node])
    const pq = new MinPriorityQueue({ priority: x => x[0] })
    pq.enqueue([0, k])

    while (!pq.isEmpty()) {
        const [d, u] = pq.dequeue().element

        if (d > dist[u]) continue // 过时路径，跳过

        for (const [v, w] of adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w
                pq.enqueue([dist[v], v])
            }
        }
    }

    // 3. 寻找结果
    let maxDist = 0
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1
        maxDist = Math.max(maxDist, dist[i])
    }
    return maxDist
}

(注：MinPriorityQueue 是 LeetCode 环境内置的库)

应用场景

• 地图导航与 GPS：计算两个地理坐标点之间的最短行驶路线。
• 网络路由协议：OSPF（开放式最短路径优先）协议使用 Dijkstra 算法来更新路由表。
• 任务调度：在有向无环图中寻找关键路径或最小化任务总时长。
• 游戏 AI：非网格类地图中，NPC 寻找通往目标点的最短路径。

Dijkstra vs Floyd

• Dijkstra：单源最短路径。速度快（优化后 $O(E \log V)$），但不能处理负权。
• Floyd：全源最短路径。代码极简，支持负权边，但速度慢（ $O(V^3)$ ），仅适用于小规模数据。

在实际开发中，如果只需要从一个点出发，优先选择 Dijkstra。