GATE CSE 2012 | Question: 40

Question

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.

• A.  $\text{SDT}$
• B.  $\text{SBDT}$
• C.  $\text{SACDT}$
• D.  $\text{SACET}$

Comments

 

It becomes easier to visualise when you work through the code as well. 

When we start at S, we set A to 4, B to 3 and D to 7 and S is deleted from the min-heap. Now, the next iteration starts by deleting B from the min-heap, as it is the smallest element. So now when we look at all the outgoing edges from B, we notice that the path via D also gives us 7. But, the question says that we will only update the path if it is strictly lesser than what we already have and hence, nothing happens and we have visited two vertices - S and B till now.

Next, we visit remove A from the min-heap and update C to 5. Next we remove C from min-heap and update E to 6. Now, the next will be E (as the value is 6, compared to value 7 of D), and we make G as 8, and T as 10. Now in the next iteration, D is picked and F is set to 12, but T is unchanged because, again, the question says that we update only if the path is strictly less than what we already have. 

---

it is because of that one edge D to E whose weight is 1, caused SACET instead SBDT as the ans.
however we reached till SBD but we found there is an edge from D to E which is smallest from all ougoing edges in E.So we considered it ( greedy approch😜) and that led us to change our whole route because cost of SACE is lesser than SBDE.

---

Actually in exam we not need to solve this question completely bzoz after solving few steps we get idea about which option will be the correct answer but instead of this if they ask about which edges willl be selected by this algo then we need to solve this question completely 

Answer 1

They did not ask about shortest paths from S to T but they had asked the shortest path obtained by applying Dijkstra algorithm. If we apply Dijkstra algorithm we got path from S to T 10 only after relaxing edges through E and E will get 6 only after relaxing edges through C and C will get 5 only after relaxing edges through A. So, the shortest path from S to T if we follow Dijkstra algorithm is S,A,C,E,T.
The shortest path between S to T is SBDT also but if you follow Dijkstra shortest path algorithm then the shortest path you will getting from S to T is only SACET. We suggest you to apply Dijkstra algorithm on S and find the shortest path between S to all vertices. Then the path you will get from S to T is SACET.


Here we will draw edge from E to T not D to S because we updated the T value to 10 after selecting vertex E.
So, path is S, A, C, E, T.
Here D will get 7 only through S. So, SBDT is not possible and SDT is not possible because T will get 10 only after selecting E. So, path is SACET.