Self-Assessment Quiz: Weighted Graphs and Shortest Paths

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+. Several questions refer to the chapter's road map:

adj = { "A": [("B", 4), ("C", 1)], "B": [("D", 1), ("E", 7)],
        "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [] }

Question 1

The weight of a path $p = v_0, v_1, \dots, v_k$ is defined as:

A) the number of edges, $k$ B) the sum of its edge weights, $\sum_{i=1}^{k} w(v_{i-1}, v_i)$ C) the largest edge weight on the path D) the number of vertices, $k+1$

Question 2

On the road map, $\delta(A, E)$ (the shortest-path distance from A to E) is:

A) 7 B) 10 C) 11 D) 8

Question 3

Relaxation of edge $(u, v)$ with weight $w$ does which of the following?

A) sets dist[v] = dist[u] + w unconditionally B) sets dist[v] = dist[u] + w only if that value is smaller than the current dist[v] C) increases dist[u] by w D) removes the edge if it is too heavy

Question 4

Dijkstra's greedy rule is: at each step, finalize the unfinalized vertex with the:

A) largest tentative distance B) most outgoing edges C) smallest tentative distance D) smallest number of edges from the source

Question 5 (True/False, justify)

True or false: A vertex should be finalized by Dijkstra the moment its tentative distance first drops below $\infty$. Justify in one sentence.

Question 6

In Dijkstra's hand trace on the road map (source A), which vertex is finalized second, and at what distance?

A) B at 4 B) C at 1 C) B at 3 D) D at 6

Question 7

The line if d > dist[u]: continue in the heap-based Dijkstra serves to:

A) detect negative cycles B) skip stale (superseded) heap entries left by lazy deletion C) terminate the algorithm early D) ensure the source is processed first

Question 8

Dijkstra's running time with a binary-heap priority queue is:

A) $O(V + E)$ B) $O(V^2)$ C) $O(E \log V)$ D) $O(VE)$

Question 9

The single step in the §29.3 correctness proof that requires non-negative weights is the inequality:

A) $\text{dist}[u] \ge \delta(s, u)$ (safety of relaxation) B) $\text{dist}[u] \le \text{dist}[y]$ (the extract-min choice) C) $\delta(s, y) \le \delta(s, u)$ (extending a shortest path cannot lower its cost) D) $\text{dist}[y] \le \delta(s, x) + w(x, y)$ (relaxation of edge $(x,y)$)

Question 10 (True/False, justify)

True or false: You can always make Dijkstra work on a graph with negative edges by adding a large constant to every edge weight. Justify in one sentence.

Question 11

Bellman-Ford performs how many full relaxation passes (before the detector pass) on a graph with $|V|$ vertices?

A) $|V|$ B) $|V| - 1$ C) $|E|$ D) $\log |V|$

Question 12

The reason Bellman-Ford needs exactly $|V| - 1$ passes is that:

A) there are $|V| - 1$ edges in any tree B) a shortest path with no negative cycle is simple, so it has at most $|V| - 1$ edges C) the heap holds at most $|V| - 1$ entries D) it matches the number of recursive calls

Question 13

After Bellman-Ford's $|V| - 1$ passes, the detector pass finds an edge $(u, v)$ that can still be relaxed. This means:

A) the algorithm has a bug B) a negative-weight cycle is reachable from the source, so some distances are $-\infty$ C) the graph is disconnected D) one more pass will fix it

Question 14

A negative cycle reachable from $s$ that can reach $v$ makes $\delta(s, v)$ equal to:

A) $0$ B) $+\infty$ C) $-\infty$ D) the cycle's weight

Question 15

Bellman-Ford's worst-case running time is:

A) $O(E \log V)$ B) $O(V + E)$ C) $\Theta(V^3)$ D) $O(VE)$

Question 16

Floyd-Warshall's recurrence is $D_{k+1}[i][j] = \min(D_k[i][j],\ D_k[i][k] + D_k[k][j])$. In this recurrence, vertex $k$ plays the role of:

A) the source of the path B) the destination of the path C) a newly allowed intermediate vertex (waypoint) D) an edge weight

Question 17 (True/False, justify)

True or false: In Floyd-Warshall, the three loops may be nested in any order as long as all three run from $0$ to $n-1$. Justify in one sentence.

Question 18

Floyd-Warshall runs in time and space:

A) $\Theta(V^3)$ time, $\Theta(V^2)$ space B) $\Theta(V^2)$ time, $\Theta(V)$ space C) $O(E \log V)$ time, $O(V)$ space D) $O(VE)$ time, $O(V^2)$ space

Question 19

Link-state routing (e.g., OSPF), in which each router learns the whole network map and computes shortest paths to all destinations locally, corresponds to which algorithm?

A) Bellman-Ford B) Floyd-Warshall C) Dijkstra D) BFS

Question 20 (Short answer)

In one sentence each: (a) Which algorithm should you choose for single-source shortest paths when all weights are non-negative? (b) Which should you choose when some edges may be negative? (c) Which is best for all-pairs shortest paths on a small, dense graph?

Answer Key

Topics to review by question