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.

Let us trace Dijkstra's algorithm step by step starting from source $S$:

1. Initialization:

   • Distances: $d(S)=0$, all others $\infty$.

2. Extract $S$ ($d=0$):

   • Relax edges from $S$:

     • $d(A) = 0 + 4 = 4$, $\text{parent}(A) = S$

     • $d(B) = 0 + 3 = 3$, $\text{parent}(B) = S$

     • $d(D) = 0 + 7 = 7$, $\text{parent}(D) = S$

3. Extract $B$ ($d=3$):

   • Relax edge $(B, D)$ with weight 4: $d(D) = \min(7, 3+4) = 7$. Since $7$ is not strictly shorter than $7$, distance and parent of $D$ are not updated.

4. Extract $A$ ($d=4$):

   • Relax edge $(A, C)$ with weight 1: $d(C) = 4 + 1 = 5$, $\text{parent}(C) = A$.

5. Extract $C$ ($d=5$):

   • Relax edge $(C, D)$ with weight 3: $5+3 = 8 > 7$ (no update).

   • Relax edge $(C, E)$ with weight 1: $d(E) = 5 + 1 = 6$, $\text{parent}(E) = C$.

6. Extract $E$ ($d=6$):

   • Relax $(E, D)$ with weight 1: $6 + 1 = 7$ (not strictly shorter, no update to $D$).

   • Relax $(E, G)$ with weight 2: $d(G) = 6 + 2 = 8$, $\text{parent}(G) = E$.

   • Relax $(E, T)$ with weight 4: $d(T) = 6 + 4 = 10$, $\text{parent}(T) = E$.

7. Extract $D$ ($d=7$):

   • Relax $(D, T)$ with weight 3: $7 + 3 = 10$ (not strictly shorter than $10$, no update to $T$).

   • Relax $(D, F)$ with weight 5: $d(F) = 7 + 5 = 12$, $\text{parent}(F) = D$.

8. Extract $G$ ($d=8$):

   • Relax $(G, T)$ with weight 3: $8 + 3 = 11 > 10$ (no update).

9. When $T$ is reached with distance 10, the parent pointers traced back are:

   $$T \leftarrow E \leftarrow C \leftarrow A \leftarrow S$$

Thus, the path found is SACET.

Therefore, (D) is the correct option.