Dijkstra 算法 vs Bellman-Ford 算法详解

1. 概述

本文将介绍两种常见的单源最短路径（SSSP）算法：Dijkstra 算法和Bellman-Ford 算法。我们将从理论原理、适用场景、优缺点等方面进行对比分析，帮助你在不同图结构中选择合适的算法。

---

2. Dijkstra 算法

2.1 原理简介

Dijkstra 算法是一种用于单源最短路径（SSSP）的经典算法，适用于非负权图。其核心思想是：

• 从起点开始，每次选择当前距离最短的节点，更新其邻居的距离。
• 使用优先队列（如最小堆）来维护待处理节点。

2.2 时间复杂度

• 时间复杂度：O(V + E log V)，其中 V 是节点数，E 是边数。
• 在稠密图中，E ≈ V²，此时复杂度约为 O(V² log V)。

2.3 适用条件

• ✅ 适用于无负权边的图。
• ❌ 无法处理负权边或负权环。

2.4 优势与局限

优势	局限
⚡ 时间复杂度低，效率高	❌ 不能处理负权边
✅ 适用于稀疏图	❌ 多源最短路径时效率不如 Floyd-Warshall

---

3. Bellman-Ford 算法

3.1 原理简介

Bellman-Ford 算法也是一种 SSSP 算法，但其核心思想是动态规划：

• 对图中所有边进行 V - 1 轮松弛操作（relaxation）。
• 若第 V 轮仍有更新，则说明图中存在负权环。

3.2 时间复杂度

• 时间复杂度：O(V * E)，适用于边数不多的图。
• 对于稠密图，性能不如 Dijkstra 或 Floyd-Warshall。

3.3 适用条件

• ✅ 支持负权边。
• ✅ 可检测负权环。
• ❌ 无法处理无向图中的负权边（会形成负权环）。

3.4 优势与局限

优势	局限
✅ 可处理负权边	⚠️ 时间复杂度较高
✅ 可检测负权环	❌ 不适用于无向图中的负权边

---

4. 示例：非负权图

考虑如下图：

Dijkstra 算法流程：

1. 起点 S 距离设为 0，加入优先队列。
2. 提取距离最小的节点，更新其邻居。
3. 重复直到队列为空。

结果：所有节点的最短路径被正确计算。

---

5. 示例：负权图（无负环）

考虑如下图：

Bellman-Ford 算法流程：

1. 初始化所有节点为 ∞，起点为 0。
2. 对所有边进行 V - 1 次松弛操作。
3. 第 V 次若仍有更新，说明存在负环。

结果：所有节点的最短路径正确，且无负环。

---

6. 示例：含负环图

考虑如下图：

Bellman-Ford 算法流程：

1. 执行 V - 1 次松弛操作。
2. 再次执行一次松弛操作。
3. 若仍有更新，说明存在负环。

结果：检测出负环 ACB，路径权值持续下降。

---

7. 对比总结

特性	Dijkstra	Bellman-Ford
非负权图	✅ 支持	✅ 支持
负权边	❌ 不支持	✅ 支持（仅限有向图）
负权环检测	❌ 不支持	✅ 支持
时间复杂度	O(V + E log V)	O(V * E)
适用图类型	有向/无向图	有向图（负权边）

---

8. 适用场景建议

• ✅ 使用 Dijkstra 的场景：

  • 图中无负权边。
  • 需要高效计算单源最短路径。
  • 稀疏图（边数远小于节点数平方）。

• ✅ 使用 Bellman-Ford 的场景：

  • 图中存在负权边。
  • 需要检测负权环。
  • 边数不多，图结构相对简单。

---

9. 小结

• Dijkstra 算法效率高，适用于大多数无负权图场景。
• Bellman-Ford 算法更灵活，能处理负权边并检测负环，但性能较差。
• 根据图的结构和需求选择合适的算法是关键。

✅ 踩坑提醒：

• 使用 Dijkstra 时务必确保图中无负权边，否则结果不可靠。
• Bellman-Ford 虽支持负权边，但不能处理无向图中的负权边，否则会误判为负环。

---

10. 附录：代码示例（Java）

Dijkstra 示例

import java.util.*;

public class Dijkstra {
    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static void dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

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

        while (!pq.isEmpty()) {
            int u = pq.poll()[0];
            for (Edge e : graph.get(u)) {
                if (dist[e.to] > dist[u] + e.weight) {
                    dist[e.to] = dist[u] + e.weight;
                    pq.offer(new int[]{e.to, dist[e.to]});
                }
            }
        }

        System.out.println("Shortest distances from source:");
        for (int i = 0; i < n; i++) {
            System.out.println("Node " + i + ": " + dist[i]);
        }
    }
}

Bellman-Ford 示例

import java.util.*;

public class BellmanFord {
    static class Edge {
        int from, to, weight;
        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static boolean bellmanFord(List<Edge> edges, int n, int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int i = 0; i < n - 1; i++) {
            for (Edge e : edges) {
                if (dist[e.from] != Integer.MAX_VALUE && dist[e.to] > dist[e.from] + e.weight) {
                    dist[e.to] = dist[e.from] + e.weight;
                }
            }
        }

        // 检查负环
        for (Edge e : edges) {
            if (dist[e.from] != Integer.MAX_VALUE && dist[e.to] > dist[e.from] + e.weight) {
                System.out.println("Graph contains negative weight cycle");
                return false;
            }
        }

        System.out.println("Shortest distances from source:");
        for (int i = 0; i < n; i++) {
            System.out.println("Node " + i + ": " + dist[i]);
        }
        return true;
    }
}

---

参考资料：

• Dijkstra 算法
• Bellman-Ford 算法
• Floyd-Warshall 算法

如需进一步学习图论算法，建议结合实际项目场景进行练习，加深理解。