GATE CS 2012 Q.40 (CS Q.40): Single-Source and All-Pairs Shortest Paths

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered.

Directed weighted graph with vertices S, A, B, C, D, E, F, G, T. Edges: S to A (4), S to D (7), S to B (3), B to S (3), A to C (1), B to D (4), C to E (1), C to D (3), D to E (1), D to T (3), D to F (5), E to G (2), G to E (2), E to T (4), G to T (3), T to F (5). — Directed weighted graph

SDT

SBDT

SACDT

SACET

Official answer and solution

Official answer: D
From: Official GATE 2012 answer key

Solution

Trace Dijkstra's algorithm from S, applying the strict-update rule, and follow the parent pointers back from T.

Edges and weights (from the figure):

From $S$ : $S \to A$ (4), $S \to D$ (7), $S \to B$ (3)
From $A$ : $A \to C$ (1)
From $B$ : $B \to S$ (3), $B \to D$ (4)
From $C$ : $C \to E$ (1), $C \to D$ (3)
From $D$ : $D \to E$ (1), $D \to T$ (3), $D \to F$ (5)
From $E$ : $E \to G$ (2), $E \to T$ (4)
From $G$ : $G \to E$ (2), $G \to T$ (3)
From $T$ : $T \to F$ (5)

Run Dijkstra from $S$ , updating a distance only when a strictly shorter path is found:

Extract $S$ (0): $d(A) = 4$ , $d(D) = 7$ , $d(B) = 3$ .
Extract $B$ (3): $B \to D$ gives $3 + 4 = 7$ , not strictly less than $7$ , so $D$ keeps parent $S$ .
Extract $A$ (4): $d(C) = 5$ via $A$ .
Extract $C$ (5): $d(E) = 6$ via $C$ ; $C \to D$ gives $8 > 7$ (no update).
Extract $E$ (6): $d(G) = 8$ via $E$ ; $d(T) = 6 + 4 = 10$ via $E$ .
Extract $D$ (7): $D \to E$ gives $8 > 6$ ; $D \to T$ gives $7 + 3 = 10$ , not strictly less than $10$ (no update); $d(F) = 12$ .
Extract $G$ (8): $G \to T$ gives $11 > 10$ (no update).
Extract $T$ (10).

The candidate paths SDT ( $7 + 3$ ), SBDT ( $3 + 4 + 3$ ) and SACET ( $4 + 1 + 1 + 4$ ) all have length $10$ , while SACDT has length $4 + 1 + 3 + 3 = 11$ . Because $T$ was first reached through $E$ and later equal-length paths do not replace it, following parents back from $T$ gives $T \leftarrow E \leftarrow C \leftarrow A \leftarrow S$ , i.e. SACET.

Final answer

Common trap

Choosing SDT or SBDT: they are also shortest (length 10), but T's distance is first set to 10 via E, and the strict-update rule never replaces it.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 40 of 65, printed as CS Q.40
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source