Dijkstra 算法在负权边下的失效问题

1. 概述

在本篇文章中，我们将探讨当图中存在负权边时，使用 Dijkstra 算法可能遇到的两个问题：

无限循环（Infinite Cycles）：如果图中包含负权环，Dijkstra 算法将无法终止。
错误路径选择（Wrong Path）：即使没有负权环，Dijkstra 也可能无法找到真正的最短路径。

我们先快速回顾 Dijkstra 算法的基本原理和实现逻辑，再深入分析其在负权图中的失效原因。

2. Dijkstra 算法回顾

2.1. 核心思想

Dijkstra 算法是一种贪心算法，用于计算单源最短路径（Single Source Shortest Path, SSSP）。给定一个图 G(V, E)，其中：

V 表示节点数量
E 表示边的数量
每条边都有一个非负权重（weight）

Dijkstra 会从一个指定的源节点出发，计算到图中所有其他节点的最短路径。

⚠️ 注意：Dijkstra 的正确性依赖于所有边的权重为非负数。

2.2. Java 实现示例

public class Dijkstra {
    public static int[] dijkstra(int V, int source, List<List<Edge>> adj) {
        int[] cost = new int[V];
        Arrays.fill(cost, Integer.MAX_VALUE);
        cost[source] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));

        pq.add(new Edge(source, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int u = current.to;

            for (Edge edge : adj.get(u)) {
                int v = edge.to;
                int newCost = cost[u] + edge.weight;

                if (newCost < cost[v]) {
                    cost[v] = newCost;
                    pq.add(new Edge(v, newCost));
                }
            }
        }

        return cost;
    }

    static class Edge {
        int to, weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
}

2.3. 正确性证明（简要）

Dijkstra 基于一个贪心思想：当前已知的最短路径是不可被超越的。也就是说，一旦某个节点被从优先队列中取出，它的最短路径就已经确定，后续不会再更新。

✅ 这个假设在所有边权为非负时成立。

但如果存在负权边，就可能出现后续路径总权值更小的情况，从而导致 Dijkstra 无法正确计算最短路径。

3. 问题一：无限循环（Infinite Cycles）

3.1. 问题描述

当图中存在负权环（Negative Cycle）时，Dijkstra 会陷入无限循环，无法终止。

✅ 负权环：图中一个环路，其所有边的总权值为负。

3.2. 示例图

Cycles

图中节点 A 为源点。运行 Dijkstra 后：

A → B → C → A 形成一个负权环
每次更新都会产生更小的 cost，导致无限循环

3.3. 踩坑提醒

❌ Dijkstra 不适用于包含负权环的图。遇到此类图，算法将永远运行下去。

4. 问题二：错误路径（Wrong Path）

4.1. 问题描述

即使图中没有负权环，只要存在负权边，Dijkstra 也可能选择错误路径，导致最终结果不准确。

4.2. 示例图

WrongPath

图中节点 A 为源点：

A → B 边权为 5
A → C 边权为 7
C → B 边权为 -4

Dijkstra 会先选 A → B（权值 5），但其实 A → C → B 的总权值是 3，更优。

4.3. 原因分析

Dijkstra 一旦将节点从优先队列中取出，就认为其最短路径已确定，不再更新。因此：

❌ Dijkstra 无法回溯更新已处理节点的最短路径，无法处理负权边带来的“后发优势”。

5. 总结

问题类型	是否会终止	是否能给出正确结果	说明
存在负权环	❌ 否	❌ 否	无限循环
存在负权边	✅ 是	❌ 否	可能选错路径
所有边权非负	✅ 是	✅ 是	标准适用场景

✅ 替代方案建议

如果图中存在负权边或负权环，应使用 Bellman-Ford 算法 或 SPFA（Shortest Path Faster Algorithm）
Dijkstra 只适用于非负权图

💡 提示：如果你不确定图中是否存在负权边，优先选择 Bellman-Ford 或 SPFA。

Persistence

REST

Security