edited by
2,163 views
0 votes
0 votes

Suppose that you are running Dijkstra’s algorithm on the edge-weighted diagram below, starting from vertex A.

 

 

The Table gives ‘Distance’ and ‘Parent’ entry of each vertex after vertex E has been deleted from the priority queue and relaxed.

Vertex Distance Parent
A 0 Null
B 2 A
C 13 F
D 23 A
E 11 F
F 7 B
G 36 F
H 19 E

 

What could be the possible value of expression x+y?

edited by

2 Answers

Best answer
4 votes
4 votes

Let's start with finding out the edge weight "x" which is relatively simple.

First,create an array  which stores a (node,distance from "A") tuple where the first element(or the destination node i.e "H") and last element(source node i.e "H").The array is sorted in reverse order where if you traverse from right to left you get the nodes which are visited en-route from "A-H".The array can be easily formed by looking at the Table given in the question.It looks like:-

Shortest Path from "A-H"
(H,19) (E,11) (F,7) (B,2) (A,0)

Now, looking back at the question,the unknown edge-weight "x" is cost of the edge connecting E-H,and from the array we can see that en-route from A-H ,E is the second last node,and it's visited just before "H".So,

$11(A-E)+x(E-H)=19(A-H)\\or,x=19-11=8$

Now,when neighbours of F were examined,(H=7(A-F)+y) must have been greater than 11,and then only E was selected as the shortest path.So, 7+y>11.

After,E has been deleted and relaxed,there was a contest between (A-E-H=19) and (A-F-H=7+y),again the latter lost ,indicating 7+y>19.


$or,y>12\\ By\:adding\:a\:on\:both\:sides\:we\:get:\\or,x+y>12+8=20(\because x=8)\\\therefore x+y \in \left \{ z:z>20 \right \}$

selected by
0 votes
0 votes
Let us follow Dijkstra's Algorithm step by step till vertex E is deleted from the Q.

Assuming $vertex  A$ as the source vertex, $decrease  key()$ is performed on vertices $B,C and D$ and the keys in min-heap will be $\begin{Bmatrix} 2,15,23,\infty ,... \end{Bmatrix}.$. Vertex B is deleted from heap. Now  $decrease  key()$ is performed on $ E $  and  $  F $ and the min heap will be $\begin{Bmatrix} 7,15,17,23,\infty ,... \end{Bmatrix}.$ Vertex F gets deleted from the min-heap.$Decrease  key()$ is performed on vertices $E,H , G$  $ and  C$ and the min-heap will be $\begin{Bmatrix} 11,13,23,36,7+y,\infty ,... \end{Bmatrix}.$ .

Definitely $7 + y > 11$, or else parent of $H$ would be $F$. Following similar steps after vertex E gets deleted the new key for $H$ is $19( =11(=7+4) + 8)$ with $parent   E$. It certainly means that $x$ is $8$. Also because parent of $H$ is $E$ it means $7 + y > 19$.  But I dont think we can pin point what $y$ will be exactly.