retagged by
642 views
0 votes
0 votes

Will dijiktras's algoritm fail for the graph given in the question (or the question has been framed wrongly)?

retagged by

1 Answer

Best answer
2 votes
2 votes

Okay. So, first thing is why and where Dijkstra is failing in current graph.

answer of where is for V. The correct shortest path cost for V is 2. P-->Q-->T-->U-->W-->V.

If the vertices are relaxed in this manner then surely the cost for V will come 2 and that is correct only.

Answer of Why is because we are relaxing S first before W.

Why we are doing that ? because the cost for S is 9 and for W is 13.

As now we are changing edge cost of Q-->S,there are two ways to solve it.

1st--> ensure that W is relaxed first. For that we have to make cost of S as 14, and for that Q-->S should be greater then 12 and less than or equal to 20. // 8 values.

2nd--> even if we relax S first , correct answer for V comes.

If we put Q-->S as -1, then cost for V will be 2. And for all values less than -1, cost will be evaluated correctly.// 20 values

So, total values are 28 (-20,-19,.....,-2,-1,13,14....19,20).

selected by
Answer:

Related questions