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

Statement  ""IN ANY ITERATION ,THE SHORTEST PATH TO A VERTEX V IS UPDATED ONLY WHEN A STRICTLY SHORTEST PATH TO V IS DISCOVERED"""​​​​​​​

 that means we have to considered only such node whose relaxation can affect/reduces /(changes to min. value than earlier)  other neighbouring  nodes along with that  it must be in shortest path(  i.e.  while relaxation of D it reduces the node value of F but cant reduces the value of T  , therefore it is not considered)

Answer 2

SACET

Answer 3

answer may be 22 ??

B-S-A-C-D-E-G-T-F

Comments

How ?

Answer 4

Answer D is correct.

D)S->A->C->E->T

Comments

can u explain how @Nagamani?

---

it is because of that one edge D to E whose weight is, 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.