edited by
26,449 views
65 votes
65 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}$
edited by

9 Answers

Best answer
59 votes
59 votes

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
21 votes
21 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.

11 votes
11 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.

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
Answer:

Related questions

71 votes
71 votes
14 answers
1
gatecse asked Sep 26, 2014
28,614 views
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is$O (n \log...
59 votes
59 votes
5 answers
2
42 votes
42 votes
4 answers
3
35 votes
35 votes
3 answers
4
gatecse asked Aug 5, 2014
15,481 views
The recurrence relation capturing the optimal execution time of the $Towers \ of \ Hanoi$ problem with $n$ discs is$T(n) = 2T(n − 2) + 2$$T (n) = 2T(n − 1) + n$$T (...