in Algorithms edited by
21,256 views
58 votes
58 votes

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.

  1.  $\text{SDT}$
  2.  $\text{SBDT}$
  3.  $\text{SACDT}$
  4.  $\text{SACET}$
in Algorithms edited by
by
21.3k views

4 Comments

@KadharHussan remember the extra condition " in any iteration, the shortest path to a vertex vv is updated only when a strictly shorter path to vv is discovered."

1
1

 

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. 

1
1
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.
0
0

8 Answers

54 votes
54 votes
Best answer

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

edited by

4 Comments

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.

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

@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)

0
0
15 votes
15 votes

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.

10 votes
10 votes

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.

4 Comments

provide some explanation on your point.
0
0
By this logic $\mathbf C$ should also be right but its not.
4
4
C is wrong ,because of the statement given in the question --> "shortest path to a vertex v is updated only when a strictly shorter path to v is discovered." So from the above mentioned approach(logic) u can only relax vertex E after C. And by this--> u'll get ans as option D .
0
0

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

0
0
2 votes
2 votes
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

4 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.
1
1

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

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

Related questions