566 views

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?

0
your table contains the distance  of D is 23 but if we run dijkastra then the distance we are getting is 20
1

I am getting $x=8$ and $y>12$.

When we run Dijkstra's algo on the original graph then we will delete vertices in the sequence $A,B\; and\;F$ and then distance matrix will be like this after relaxation :-

A B C D E F G H
13 23 11   36 7+y

Now, Either $E$ will be deleted or $H$. $H$ will be deleted if $y \leq 4$ but value of $H$ is given as $19$ So, It must be deleted after $E$ because if it is deleted before $E$ then it should be fixed as $11$.

Now, after deletion of $E$ from min-heap, distance matrix after relaxation should be :-

A B C D E F G H
13 23     36 min(7+y,11+x)

So, from the given table, $min(7+y,11+x)=19$

But it is given in the table that parent of $H$ is $E$, So, $11+x=19$ and $7+y >19$

So, $x=8$ and $y>12$ and possible values of $x+y$ can be $21,22,23,...$

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

 (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
2

Thanks @Debdeep1998 , @ankitgupta.1729 i also got the same equations but i thought there was some way to get exact value of Y. but my doubt is cleared.

1

@noob_coder

then select this answer as BEST :)

## Related questions

1
129 views
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?
1 vote
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????