The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
3.3k views

Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to

  1. only vertex $a$

  2. only vertices $a, e, f, g, h$

  3. only vertices $a, b, c, d$

  4. all the vertices

asked in Algorithms by Veteran (68.8k points)
retagged by | 3.3k views
explain this with diagram plz

not get the point why d is correct

3 Answers

+22 votes
Best answer
D.  all the vertices. Just simulate the Dijkstra's algorithm on it. Dijkstra's algorithm is not meant for graphs with negative-edge-weight-cycle, but here it does give the correct shortest path.
answered by Veteran (332k points)
edited by
e is already -2 rt? So, -1 needn't be assigned.

no it does not fail... 

e= -2 in 2nd pass and in 7th pass it -1 but -2 is less than -1 so we need not to relax it ..

so it work fine ...

Works for this example, Hence D is the answer. But Dijkstra's may not work correctly for all graphs with negative weights (with our without cycle)

ref:- https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Related_problems_and_algorithms
@Arjun sir,

Dijkstra cannot work for negative edge weights.

Here, bychance it worked for A , we got correct result.

But, if we take D as source, then D -> H path we get = 2 but there is even a different path = 0.

So, surely it did work for A here, but not for all other edges , which means dijkstra must never be used for negative edge weights ?

Am i thinking right sir..??
D -> H =4 rt?

but other way it is 0

So, 0<4

So, it will take minimum path 0

Then here it will work for -ve weight cycle too.
arjun sir, Dijsktra algorithm cannot compute the shortest path in case of negative weight cycles as it cannot detect them but it will definitely compute shortest path in case of negative weight edges. So can we answer directly even without computing??

@sushmita, No. Why Dijstra will work in -ve edges ?.
It may fail in -ve edge even there is no -ve cycle.


Can u calculate distance from A to C using Dijkstra ?, It will be 2, right ?
But actual shortest distance is 1 only. (Here Dijkstra fails even NO cycle.)

Here whats happening, Observe:-

Dijkstra had 2 choices to go to C from A, It chooses direct path.
It says if I go via B, then i would have to incur ATLEAST 5 cost. (it don't know that in future there may be a -ve edge.)
It thinks, A to B distance itself is 5 and if I go via B then cost would always increese, there is no chance of decrease. but to his surprise I put "-4"

Actually Dijkstra assumes that all edges are +ve. (if u see proof of " correctness of Dijkstra" then first assumption is weights are +ve )

yeah u r right. thanx a lot. i was mistaken. very nice example. thanx again.

Will this be the graph with shortest path estimates?

There is no negative edge cycle in above graph, Dijkstra alto doesn't work for those graph which have negative edge cycle which is not present in the given graph.
So you are saying that this graph is correctly drawn?
@Sachin, going by your logic here answer should not be D. What's correct? I'm confused.
@Swati there is nothing to be confused. Dijkstra's algo only fail when negative edge cycle present in the graph , as we can see there is no negative edge cycle in the graph , for better understanding you can try to simulate the Dijkstra's algo on given graph.

I'm getting below shortest path graph. Is it correct?

@Sachin Mittal, for the graph given by you, isn't following solution work?

@swati you have take weight of e-f edge equals to 1 but in the question it is given 2, correct that and simulate the algo again .
@Rahul The question book from where I'm doing, (e-f)=1 only. Now I get why am I getting different answers from other commentators here.
@swati you may get the different answer but I think it will still give shortest path .
0 votes

Just quickly check for negative edge weight cycle. If no negative edge weight cycle then  Dijkstra's algo. will work fine.

If you are not confident in detected cycle( or cycle detection) then simulation of Dijkstra's algo. is done in below image. 

 

answered by Veteran (11.7k points)

@Chhotu

can yu just tell how to quickly check for negative edge weight cycle?

–1 vote
Dijkstra's single source shortest path algorithm here this works fine bcoz there is no -ve weight cycle in graph.
answered by Junior (577 points)
D is the correct option, but the explanation you have provided does not seem right.
Just see the diagram by Sachin Mittal bro. Even if there is no negative weight cycle still only negative edges can also give wrong answer.

So if they are asking about shortest path with negative edges then there is no method or rule except applying Dikastras algo & verifying manually if it is the correct answer.


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

32,505 questions
39,217 answers
109,115 comments
36,599 users