CS61B 课程笔记（Lecture 29 Shortest Paths)

介绍

本节讨论最短路径算法，包括Dijkstra算法和 A* 算法。

回顾

我们已掌握的方法包括：

  1. 从给定顶点 s 找到所有可达顶点的路径。
  2. 从给定顶点 s找到所有可达顶点的最短路径。

搜索方法

我们可以使用两种搜索方法：

  • 广度优先搜索（BFS）：用于寻找最短路径。
  • 深度优先搜索（DFS）：不一定找到最短路径。

效率比较

  • 在空间复杂度上，DFS 在稀疏图中表现较差，因为会产生大量递归调用。
  • BFS 在“灌木状”图中效率较低，因为使用了较多的队列。

DFS 在稀疏图中的表现

深度优先搜索（DFS）

  • 工作原理：DFS 是一种通过递归或栈结构来访问图中节点的方法。它尽可能深地探索每一条路径，直到没有未访问的相邻节点为止，然后回溯到上一个节点，继续探索其他路径。

  • 空间复杂度：DFS 的空间复杂度主要由两个因素决定：

    • 递归调用栈：每进行一次递归调用，程序都会在调用栈中存储当前状态。对于深度为 d 的树（图）的 DFS，最坏情况下（例如，树呈现出极长的链状结构），调用栈的深度也会达到 \(d\)，因此空间复杂度为 \(O(d)\)。
    • 边的存储：在稀疏图中，边的数量远小于节点数量，即 \(E << V\)，但由于递归调用的栈空间会受到影响，递归深度可能会增大，导致总体空间使用较大。

  • 总结：在稀疏图中，由于节点数量相对较少，但每个节点的递归调用可能会导致深度非常大，因此会产生大量的递归调用，导致空间复杂度较高。

BFS 在“灌木状”图中的效率

广度优先搜索（BFS）

  • 工作原理：BFS 是一种通过队列结构来访问图中节点的方法。它首先访问起始节点，然后逐层向外扩展，逐一访问当前层所有未访问的相邻节点。

  • 空间复杂度：BFS 的空间复杂度主要受以下因素影响：

    • 队列：BFS 使用队列来存储待访问的节点。最坏情况下，在某一层，队列中可能存储大量的节点。
    • 节点数：在“灌木状”图中，某些节点的分支数可能非常高，导致一层的节点数量急剧增加，这样队列会迅速变大，消耗大量内存。

  • 总结：在“灌木状”图中，分支较多的节点使得每一层的节点数目增大，从而增加了队列的存储需求，这导致 BFS 的空间复杂度增加，效率降低。

整体比较

  • DFS 在稀疏图：由于稀疏图的边较少，`DFS 可能需要更多的递归调用来探索深度，这会导致较高的空间消耗。
  • BFS 在“灌木状”图：由于“灌木状”图的节点分支较多，BFS 在每一层都需要维护大量的节点在队列中，从而导致更高的空间需求。

总结

  • DFS 适合在边比较稠密的图中，因为其使用的空间主要依赖于递归深度。
  • BFS 更适合于边比较稠密、层次分明的图，但在分支较多的“灌木状”图中，由于需要存储大量节点，可能会变得低效。

神秘问题

我们是否开发了一个算法来找到从给定顶点到所有其他可达顶点的最短路径？答案是部分肯定。我们开发的算法适用于没有边权重的图，只能找到从源顶点到每个可达顶点的边数最少的路径。

但当图的边具有权重时，我们需要一个不同的算法来找到最短路径。

Dijkstra 算法

观察

  • 最短路径可能包含许多边，我们关注的是路径上边权重的总和。
  • 从源顶点 s到每个其他顶点 v 的最短路径可以通过以下方式构建：
    1. 找到从 s 到 v 的最短路径。
    2. 组合所有找到的边，形成“最短路径树”。

Dijkstra 算法步骤

  1. 创建优先队列。
  2. 将源顶点 s 添加到优先队列，优先级为 0。将所有其他顶点添加到优先队列，优先级为 ∞。
  3. 当优先队列不为空时：
    • 从优先队列中弹出一个顶点，并放松所有出发边。

放松操作

“放松”涉及检查边以优化到达某个顶点的当前已知最短路径。如果通过某条边可以使到达目标顶点的路径更短，则更新该顶点的最短路径。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def dijkstras(source):
    PQ.add(source, 0)
    For all other vertices, v, PQ.add(v, infinity)
    while PQ is not empty:
        p = PQ.removeSmallest()
        relax(all edges from p)

def relax(edge p, q):
   if q is visited (i.e., q is not in PQ):
       return

   if distTo[p] + weight(edge) < distTo[q]:
       distTo[q] = distTo[p] + w
       edgeTo[q] = p
       PQ.changePriority(q, distTo[q])

最优性证明

假设所有边的权重为非负值：

  • 初始时，源顶点的距离为 0，最优。
  • 经过放松操作后，权重最小的顶点 $v_1 $ 是从源顶点的最短路径。

不可变性

一旦一个顶点从优先队列中弹出，就不会被重新添加，距离也不会更新。这意味着一旦弹出，已知从源到该顶点的最短距离。

下面是 Dijkstra 算法的 Java 实现代码，这个实现使用优先队列来管理顶点的优先级，并利用一个图的邻接列表表示法来存储边。

Dijkstra 算法的 Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.util.*;

class Dijkstra {
    private static class Edge {
        int target;
        int weight;

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

    private final List<List<Edge>> graph; // 邻接列表表示的图

    public Dijkstra(int vertices) {
        graph = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
    }

    // 添加边到图
    public void addEdge(int source, int target, int weight) {
        graph.get(source).add(new Edge(target, weight));
    }

    // Dijkstra 算法
    public int[] shortestPath(int source) {
        int vertices = graph.size();
        int[] distTo = new int[vertices];
        Arrays.fill(distTo, Integer.MAX_VALUE);
        distTo[source] = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(v -> distTo[v]));
        pq.add(source);

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

            // 遍历当前顶点的所有邻接边
            for (Edge edge : graph.get(current)) {
                relax(current, edge.target, edge.weight, distTo, pq);
            }
        }

        return distTo;
    }

    // 放松操作
    private void relax(int p, int q, int weight, int[] distTo, PriorityQueue<Integer> pq) {
        if (distTo[p] + weight < distTo[q]) {
            distTo[q] = distTo[p] + weight;
            pq.add(q); // 更新优先队列
        }
    }

    // 测试 Dijkstra 算法
    public static void main(String[] args) {
        Dijkstra dijkstra = new Dijkstra(5);
        dijkstra.addEdge(0, 1, 10);
        dijkstra.addEdge(0, 2, 3);
        dijkstra.addEdge(1, 2, 1);
        dijkstra.addEdge(1, 3, 2);
        dijkstra.addEdge(2, 1, 4);
        dijkstra.addEdge(2, 3, 8);
        dijkstra.addEdge(2, 4, 2);
        dijkstra.addEdge(3, 4, 7);
        dijkstra.addEdge(4, 3, 9);

        int[] distances = dijkstra.shortestPath(0);

        // 输出从源顶点 0 到其他顶点的最短距离
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < distances.length; i++) {
            System.out.println(i + " \t\t " + distances[i]);
        }
    }
}

代码说明

  1. Graph Representation: 使用邻接列表来表示图，每个节点存储到其邻接节点及相应权重的边。

  2. Adding Edges: addEdge 方法用于添加一条边。

  3. Dijkstra's Algorithm:

    • shortestPath 方法初始化距离数组，并使用优先队列管理待处理的节点。
    • 通过 relax 方法对每一条边进行放松操作，更新距离。

  4. Relaxation: relax 方法检查通过某条边到达目标节点的距离是否更短，如果更短则更新。

  5. Testing: 在 main 方法中创建一个图并执行 Dijkstra 算法，最后输出从源顶点到其他顶点的最短距离。

运行结果

当运行上述代码时，会输出源顶点到其他所有顶点的最短距离。例如，如果源顶点是 0，输出可能如下所示：

1
2
3
4
5
6
Vertex Distance from Source
0              0
1              7
2              3
3              9
4              5

这个结果表明，从顶点 0 到顶点 1 的最短路径长度为 7，以此类推。

A*算法

在 Dijkstra 算法的基础上，A* 算法引入了启发式估计，可以更快地找到目标顶点。

启发式问题

在A*算法中，需要估算目标距离。如果估算错误，可能导致算法无法找到最短路径。

启发式条件

  1. 可接受性：估算值应小于等于真实距离。
  2. 一致性：对于所有节点，估算值应满足三角不等式。