search
Log In
0 votes
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?

in Algorithms 566 views
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,...$

1 Answer

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

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

0 votes
2 answers
1
129 views
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?
asked Jan 26, 2019 in Algorithms screddy1313 129 views
1 vote
1 answer
2
1 vote
2 answers
3
215 views
Consider a weighted, directed acyclic graph G = (V,E,w) in which edges that leave the source vertex s may have negative weights and all other edge weights are nonnegative. Does Dijkstra’s algorithm correctly compute the shortest-path weight δ(s,t) from s to every vertex t in this graph? Justify your answer
asked Jan 3, 2018 in Algorithms pranab ray 215 views
1 vote
1 answer
4
1.1k views
Which of the following statements is true? Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to minimum cost spanning tree. Assume unique weights. Complete graph with 4 vertices, each edges having same weights can have maximum ... no negative cycles). None of these how is 3rd wrong? If there is no negative cycles dijkstra can work just fine right?
asked Jan 20, 2017 in Algorithms Pankaj Joshi 1.1k views
...