GATE CSE 2004 | Question: 44

Question

Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source.

In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

• A. $P,Q,R,S,T,U$
• B. $P,Q,R,U,S,T$
• C. $P,Q,R,U,T,S$
• D. $P,Q,T,R,U,S$

Comments

B

---

Helpful explanation

https://www.youtube.com/watch?v=DZqwxKsPGjA&t=332

---

We can do it using Topological Sort updating distance from nodes we visit and then take shortest distance node.

Answer 1

Answer is (B). In Dijkstra's algorithm at each point we choose the vertex with the shortest distance from the set of vertices in the shortest path found so far and add the edge connecting it to the shortest path.

Comments

here i am not getting how u to s is possible as it is directed?

---

So this means that direction wont be considered here...

 

---

@pavansan we're doing P->Q-> R ->S right? 

Answer 2

Answer will be "B" 

Answer 3

 

Option B :

Answer 4

\[
\text{Just select the Minimum at each level , it will be the order of the finalization of the nodes.

This is the approach that's why priority queue is used in Dijkstra it selects the finalized (minmum)}
\]

\[
\begin{array}{|c|c|c|c|c|c|c|}
\hline
\textbf{Step} & \textbf{Finalized Node} & \textbf{Distance} & B & C & D & E \\
\hline
0 & - & A=0 & \infty & \infty & \infty & \infty \\
1 & A & A=0 & 4 & \infty & \infty & \infty \\
2 & B & B=4 & 4 & 6 & \infty & \infty \\
3 & C & C=6 & 4 & 6 & 7 & \infty \\
4 & D & D=7 & 4 & 6 & 7 & 9 \\
5 & E & E=9 & 4 & 6 & 7 & 9 \\
\hline
\end{array}
\]