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?

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,...$

4 votes

Best answer

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 \}$

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.