卷別

資料結構與演算法

選擇

國立臺灣大學 2025 · 考試 · 第 13 題

(5 points) Consider the (incomplete) pseudocode snippet SOLVE().

1: function SOLVE(G = (V, E, w), s, r)
2:     P = V                                       ▷ Initializes all vertices.
3:     Set A[s] = 0 and A[x] = ∞ for all x ≠ s.    ▷ Initializes an array A.
4:     while P ≠ ∅ do
5:         x = argmin_{x ∈ P} A[x]                 ▷ Chooses a vertex.
6:         P = P − {x}                             ▷ Removes the vertex.
7:         for each y ∈ P such that {x, y} ∈ E, do
8:             (*)
9:     return (**)

You have realized that this code snippet can be used to solve different problems by filling the blanks in different ways. Here are three problems to consider:

In the ST-DISTANCE problem, you are given a graph $G$ with non-negative weights, and two vertices $s, t \in V$ . The goal is to compute the shortest distance between $s$ and $t$ .
In the ST-BOTTLENECK problem, you are given a graph $G$ with non-negative weights, and two vertices $s, t \in V$ . The goal is to compute the smallest possible weight $wgt$ such that there exists at least one path from $s$ to $t$ using only edges whose weights are less than or equal to $wgt$ .
In the MST problem, you are given an undirected, weighted, and connected graph $G$ . The goal is to compute the total weight of a minimum spanning tree.

Select all correct statement(s) below.

(A)
To solve ST-DISTANCE, we fill $(\ast)$ with $A[y] = A[x] + w(x, y)$ , and we fill $(\ast\ast)$ with $A[t]$ .
(B)
To solve ST-BOTTLENECK, we fill $(\ast)$ with $A[y] = \max\{A[y], \min\{A[x], w(x, y)\}\}$ , and we fill $(\ast\ast)$ with $A[t]$ .
(C)
To solve MST, we fill $(\ast)$ with $A[y] = \min\{A[y], w(x, y)\}$ , and we fill $(\ast\ast)$ with $A[t]$ .
(D)
The code snippet can be implemented with Fibonacci heaps, so there exist algorithms with running time $O(|E| + |V| \log |V|)$ for all three problems stated above.
(E)
The value $A[t]$ will always be non-negative in any correct implementation for solving any of the problems stated above.

標準解析

AI 已複查