@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**."

Dark Mode

21,256 views

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.

- $\text{SDT}$
- $\text{SBDT}$
- $\text{SACDT}$
- $\text{SACET}$

@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

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

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.

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

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**

6

edited
Dec 11, 2022
by Abhrajyoti00

@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

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.

**T**here for shortest path using Dijkstra Algorithm is SACET.

10 votes

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

Answer seems to be D. could be checked directly.