The Gateway to Computer Science Excellence
0 votes
290 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 by Junior (657 points) | 290 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 \}$

by Junior (909 points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,597 answers
195,838 comments
102,143 users