Dijkstra 算法怎么求单源最短路径？为什么不能处理负权边？

简化版

Dijkstra 求「一个起点到所有点的最短路径」，用贪心 + 优先队列：每次从「还没确定的点里挑当前距离起点最近的」，把它的最短距离确定下来，再用它去松弛（更新）邻居的距离。因为它假设「已确定的点的最短距离不会再变小」，所以不能处理负权边（负权可能让已确定的点还能变得更短）。用小顶堆实现是 O((V+E) log V)。

详细版

int[] dijkstra(int n, List<int[]>[] adj, int src) { // adj[u] = {v, w}
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // 小顶堆按距离排序：{距离, 节点}
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;          // 过期的旧记录，跳过
        for (int[] e : adj[u]) {            // 松弛邻居
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

核心两步循环：取距离最小的未确定点 → 松弛它的邻居。

完整版教学

一、Dijkstra 的贪心思想

Dijkstra 维护一个 dist[] 数组（起点到各点的当前最短距离）。它的贪心策略是：在所有”还没最终确定”的点里，当前 dist 最小的那个，它的 dist 就已经是最终最短距离了，可以确定下来。

为什么这个贪心成立？因为在非负权的图里，从起点到这个「当前最近点」的路径，不可能再通过其它更远的点绕出一条更短的路（绕路只会更长，因为边权非负）。确定它之后，用它去更新（松弛）邻居：如果「经过它到邻居」比邻居当前的 dist 更短，就更新。

二、松弛（relax）操作

松弛是最短路算法的通用动作：对边 (u, v, w)，如果 dist[u] + w < dist[v]，说明「先到 u 再到 v」比「当前记录的到 v」更短，就更新 dist[v] = dist[u] + w。Dijkstra 每确定一个点，就用它松弛所有邻居，逐步把最短距离「传播」出去。

三、为什么不能有负权边（核心）

Dijkstra 的正确性完全依赖「已确定的点，其最短距离不会再变小」 这个假设。而这个假设只在边权非负时成立。

如果存在负权边，一个已经被「确定」的点，可能后来通过一条负权边发现了更短的路径——但 Dijkstra 已经把它标记为确定、不再更新了，于是给出错误结果。

举个直觉例子：A→B 权 1，A→C 权 5，C→B 权 -10。Dijkstra 会先确定 B 的距离为 1（因为 1 < 5），但实际上 A→C→B = 5 + (-10) = -5 更短，已确定的 B 却不会再被修正。所以有负权边要用 Bellman-Ford 或 SPFA。

四、优先队列优化

朴素 Dijkstra 每次「找当前最小的未确定点」要扫一遍所有点，O(V²)。用小顶堆（优先队列） 把「找最小」降到 O(log V)：

堆里存 {当前距离, 节点}，每次弹出距离最小的。
松弛成功就把新距离入堆。
因为一个点可能被多次入堆（不同时刻的距离），弹出时要判断 d > dist[u] 跳过过期记录（懒删除）。

复杂度降到 O((V+E) log V)，适合稀疏图。稠密图用朴素 O(V²) 反而可能更好。

五、复杂度与应用

优先队列版：O((V+E) log V)，稀疏图首选。
朴素版：O(V²)，稠密图可用。
应用：地图导航（最短/最快路线）、网络路由（OSPF 协议基于 Dijkstra）、游戏寻路（配合 A*）。

六、常见误区与追问

考点	正确口径
初始化	源点距离 0，其余无穷大
贪心选择	每次确定当前最短的未确定点
松弛	用当前点尝试更新邻居距离

dist[src] = 0
while pq not empty:
  u = poll min dist
  for edge u -> v:
    if dist[v] > dist[u] + w:
      relax v

Dijkstra 的贪心成立依赖一个前提：边权非负，已确定点不会再被更短路径推翻。

误区：Dijkstra 可以处理负权边。 负权边可能让已确定的最短距离之后变得更小，破坏贪心前提。
误区：优先队列里一个点只能出现一次。 常见实现会多次入队，弹出旧距离时用 if d > dist[u] continue 跳过。
误区：松弛就是访问邻居。 松弛是发现更短路径时更新 dist[v]，并把新候选放入队列。
追问：为什么不能用普通队列？ 普通队列不能保证每次取出当前距离最小的点，带权图会错。
追问：复杂度是多少？ 邻接表加优先队列常写 O((V+E) log V)，具体与堆实现有关。
追问：有负权边该用什么？ 单源可用 Bellman-Ford 或 SPFA 变体，所有点对可考虑 Floyd。

七、加强记忆

Dijkstra 求单源最短路（非负权）：贪心 + 优先队列——每次取「未确定点中 dist 最小的」确定其最短距离，再松弛其邻居。不能处理负权边：它假设「已确定点的距离不再变小」，负权会打破这个假设导致错误（负权用 Bellman-Ford）。小顶堆优化到 O((V+E) log V)，弹出时跳过过期记录。应用于导航、路由、寻路。

简化版

详细版