IS CS-2018S1-01

题目来源：Problem 1 日期：2024-08-07 题目主题：CS-算法-图论

解题思路

在解决这道题目时，我们需要理解 Dijkstra 算法的工作机制，包括初始化步骤、选择最小路径顶点的过程，以及更新路径长度的方式。通过示例和伪代码，我们可以全面理解该算法的正确性和时间复杂度。

Solution

Question 1

An example where Dijkstra’s algorithm does not find the correct shortest paths is when the graph contains negative edge weights. However, since Dijkstra’s algorithm is not designed to handle negative weights, we will use a non-negative example where it might fail due to not updating paths correctly.

Consider the following graph:

• Vertices: $V=\{A,B,C\}$
• Edges with weights: $(A\to B,1),(B\to C,-2),(A\to C,4)$

Starting from vertex $A$, Dijkstra’s algorithm will proceed as follows:

1. Initialize: $c[A]=0,c[B]=\infty ,c[C]=\infty$.
2. Choose $A$: Update $c[B]=1$ and $c[C]=4$.
3. Choose $B$: Dijkstra’s algorithm won’t update $c[C]$ to $-1$ since it already has $c[C]=4$.

In this example, Dijkstra’s algorithm does not find the correct shortest path due to the presence of a negative edge.

Question 2

To fill in the blank $[a]$, we need to correctly update the path lengths using the Dijkstra’s algorithm rule. The pseudo-code line should be:

if c[u] > c[v] + d(v, u) then c[u] = c[v] + d(v, u)

So the filled-in pseudo-code is:

Dijkstra( graph G = (V,E), start node s, length d(u,v) of each edge (u,v) ) {
    c = an empty array;    Q = an empty set;
    for ( v ∈ V )
        c[v] = ∞;
    c[s] = 0;
    for ( v ∈ V )
        add v to Q;
    while ( Q ≠ ∅ ) {
        v = a vertex v ∈ Q that minimizes c[v];
        remove v from Q;
        for ( u ∈ {destinations of edges outgoing from v} )
            if c[u] > c[v] + d(v, u) then c[u] = c[v] + d(v, u);
    }
}

Question 3

Let’s apply Dijkstra’s algorithm to the given graph:

• Start at node $S$.

Initialization:

• $c[S]=0$, $c[A]=\infty$, $c[B]=\infty$, $c[E]=\infty$.

Iteration 1:

• Choose $S$: $c[S]=0$.
• Update $c[B]=3$, $c[A]=6$, $c[E]=9$

Iteration 2:

• Choose $B$: $c[B]=3$.
• Update $c[A]=5$ (since $3+2<6$).

Iteration 3:

• Choose $A$: $c[A]=6$.
• Update $c[E]=8$ (since $6+2<9$).

Iteration 4:

• Choose $E$: $c[E]=8$.

Final values:

• $c[S]=0$, $c[A]=6$, $c[B]=3$, $c[E]=8$.

Question 4

Time complexity of the code fragments:

(i): Finding the vertex $v\in Q$ that minimizes $c[v]$ takes $O(|V|)$ time for each iteration. Since there are $|V|$ vertices, the total time spent is $O(|V{|}^2)$.

(ii): For each vertex $v$, we consider all outgoing edges $(v,u)$. Each edge is considered exactly once, hence the total time spent is $O(|E|)$.

Question 5

Using a priority queue (binary heap) as $Q$:

(i): Extracting the minimum element from the priority queue takes $O(\log |V|)$ time. Since we perform this operation $|V|$ times, the total time spent is $O(|V|\log |V|)$.

(ii): Each edge relaxation operation (updating the distance) involves updating the priority queue, which takes $O(\log |V|)$ time. Since there are $|E|$ edges, the total time spent is $O(|E|\log |V|)$.

知识点

图论Dijkstra算法时间复杂度

解题技巧和信息

1. Dijkstra 算法的限制：Dijkstra 算法不能处理带有负权边的图。
2. 复杂度分析：使用普通数组时，Dijkstra 算法的时间复杂度为 $O(|V{|}^2)$；使用优先队列时，时间复杂度为 $O(|V|\log |V|+|E|\log |V|)$。
3. 边松弛操作：每次从源顶点到目标顶点更新路径长度时，都需要检查并更新最短路径以及顶点的优先队列。

重点词汇

1. Shortest path 最短路径
2. Weighted graph 加权图
3. Priority queue 优先队列
4. Edge relaxation 边松弛
5. Computational complexity 计算复杂度

参考资料

1. Introduction to Algorithms, 3rd Edition, Chapter 24: Single-Source Shortest Paths