GATE CSE 2012 | Question : 40

Answer 1

Relaxation at every vertex is as follows:

Note that the next picked vertex corresponds to the next row in Table
$$\scriptsize{\begin{array}{|c|c|} \hline \text{} & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} & \textbf{F} & \textbf{G} & \textbf{T} \\\hline 
\textbf{S} & \text{4} &  \boxed{\text{$3$}} & \text{$\infty$} & \text{7} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$}\\
&S\to A&\boxed{\bf{S\to B}}&&S \to D\\
\\\hline  
\textbf{B} &  \boxed{\text{$4$}} &  & \text{$\infty$} & 7 & \text{$\infty$} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$}\\
&\boxed{\bf{S \to A}} &&& S \to D  \\\hline 
\textbf{A} & \text{} &  \text{} & \boxed{5} & \text{7} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$}\\
&&&\boxed{\bf{S\to A \to C}}&S \to D
\\\hline 
\textbf{C} & \text{} &  \text{} & \text{} & \text{7} & \boxed{6} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$}\\
&&&&S \to D&\boxed{\bf{S\to A\\\to C\to E}}\\
\hline 
\textbf{E} & \text{} &  \text{} & \text{} & \boxed{\text{$7$}} & \text{} & \text{$\infty$} & \text{$8$} & \text{$10$} \\
&&&&\boxed{\bf{S \to D}}&&&S\to A \to C &S\to A \to C
\\&&&&&&&\to E \to G &  \to E \to T
\\ \hline  
\textbf{D} & \text{} &  \text{} & \text{} & \text{} & \text{} & \text{$12$} & \boxed{8} & \text{$10$}\\
&&&&&&{S \to D \to F}&\boxed{\bf{S\to A \to C\\ \to E \to G}}&S\to A \to C\\
&&&&&&&& \to E \to T
\\\hline  
\textbf{G} & \text{} &  \text{} & \text{} & \text{} & \text{} & \text{12} & \text{} & \boxed{10}
\\
&&&&&&{S \to D \to F}&&\boxed{\bf{S\to A \to C \\\to E \to T}}
\\\hline  
\textbf{T} & \text{} &  \text{} & \text{} & & \text{} & \boxed{\text{12}} & \text{} & \text{}\\
&&&&&&\boxed{\bf{S \to D \to F}}&\\
\hline \end{array}}$$

For $S$ to $T$ shortest path is $\boxed{S \to A \to C \to E \to T}$

Option : D

Comments

For step 1: why B(though S->B path with wt 3) is taken out compared to S->A with wt 4?

---

it's because Dijkstra’s shortest path Algo Says always relax the min from the source and add that to visited now compare the min from newly added vertex and previous vertex from source and do relaxation bcz of that vertex at every node  .........if same or more no change ...if less Change the value of the vertex 

---

Hi , I didn't get this point. Why B is skipped and A is selected .Could you please explain in details.

---

Because we have to see S to T therefore we will see the relaxation on T which are done by SAEC.

---

@abhijit Vertex B is nor skipped when you will follow the dijkstra algo. Then DISTANCE OF D already 7 fRom S so wont be updated during relaxation of B so after completing the dijkstra u will  SACET minimum path for s to T.

---

@khushtak b is skipped in first pass which contradict this algo.

---

Dijkstra's sequence will be S, B, A, C, E, D, G, T, F but our problem is to find the shortest path from S to T.

Using the above table you can find easily.

first, go to the column of T and see the last entry cost = 10 and parent is E.  It means E -> T.

Now again go to the column of E and see the last entry cost = 6 and parent is C. It means  C -> E

and Hence C -> E -> T

Now again go to the column of C and see the last entry cost = 5 and parent is A. It means A -> C

and Hence A -> C -> E -> T

Now again go to the column of A and see the last entry cost = 4 and parent is S. It means  S -> A.

and Hence Path is S -> A -> C -> E -> T

total cost is 4 +  1 + 1 + 4 = 10.

---

there is typo in second last row of table it should be G and not E.

---

adding bit more description to above answer , 

even though option a ,b ,d all three 

1.  SDT
2.  SBDT
3.  SACET

gives 10 .

but we first found distance 10 path to T via SACET

hence even if nodes are confirmed in sequence SBACEDGTF 

i.e D confirmed after E , path to T don't go via SDT.

---

WHY NOT A OPTION , i AM GETTING SDT AS 10 WEIGHT CAN ANYONE CLEAR MY DOUBT?

---

@shivmodi94 SDT is a possible shortest path for sure, but Dijkstra won't update the parent of T as D, as after relaxing the edge D->T the distance to T still remains 10. Moreover, A,C,E will be picked before D as their weights are less than D(min heap implementation)

---

wow ,  great thanks , really your answered helped me in understanding concept. @Shubhodeep

Answer 2

Chosen answer is best one but many people have doubt that why B is not selected as it is shortest than A.

Answer to this is when we run dijkstra algorithm 

First S will update A ,B,D as 4,3,7 respectively.

then we select shortest of it i.e B (3). After there is nothing for B to relax and give better update.as D is already updated by S with weight  7. 

So now it will select A . it will relax C and so on...

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

please follow given tree. how algorithm will proceed and relax.

 

                                                             S

                                                    /         \         \

                                                 A          B          D

                                                /                           \

                                             C                              F

                                              |

                                             E

                                          /      \

                                       G         T

There for shortest path using Dijkstra Algorithm is SACET.

Comments

really good explanation!

---

easy explanation thanks

---

Great answer !!

Answer 3

Dijkstra algorithm is such that it selects shortest edge for adjacent nodes.

It selects shortest path having maximum number of shortest edges, for non adjacent.

Answer seems to be D. could be checked directly.

Comments

`JEET

Distance of option C is 11. Distance of option A=B=D=10. D is the path containing maximum number of edges.  

---

Because of this concept C option should also correct but that is not correct.

For correct answer. We should draw  the all path from S to U .  and  also than check the reverse also . From viewing from T We find the correct path is Option D.

---

your second statement is  misleading or incomplete.
If two paths have the same total cost, Dijkstra’s may choose any of them —
it doesn’t prefer the one with more or fewer edges.

Answer 4

Ans is d

But its taking too much time for me to get the ans..what is the best way to solve this question with optimal time.can any1 suggest

Comments

Before going for tricks try to solve and practice such kind of questions Using Algorithm.Once you confident about working of algorithm trust me you wont require any tricks.

---

@Rupie_c people like you makes this GO platform exceptionally awesome✌

---

use the table method without writing the paths...then use the logic in ankitron’s comment above to find the shortest path

Answer 5

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 6

SACET

Comments

D will be connected with F