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

retagged | 4.3k views
0
explain this with diagram plz

not get the point why d is correct

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.
edited by
+2
e is already -2 rt? So, -1 needn't be assigned.
+4

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

0
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
+2
@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..??
+1
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.
0
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??
+47

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

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

Will this be the graph with shortest path estimates?

0
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.
0
So you are saying that this graph is correctly drawn?
0
@Sachin, going by your logic here answer should not be D. What's correct? I'm confused.
0
@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.
+1

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

+2

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

0
@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 .
0
@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.
0
@swati you may get the different answer but I think it will still give shortest path .
0
0
@swati e to f distance is 2

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.

0

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

Dijkstra algorithm fails when the graph contains negative weight cycle forms . The graph contains only negative weights then the dijkstra gives correct shortest paths from source to every edge. so the answer is D.

Once, we know the proof of correctness of Dijkstra algorithm, it is easier to trace down why this works fine for source vertex A and not for Source Vertex D.

So, above is a snip from cormen, where Set S indicated the set of vertices for which shortest path from source vertex "s" have been determined and for $\forall v \in S$ we have $v.d=s(s,v)$ means in simple words the cost to reach every vertex in Set S, from source vertex "s" is correctly determined and they are valid under all circumstances.

Now, this proof says when suppose a new vertex say "y" is added to set S, after this is done, $y.d=s(s,y)$ holds. Means my algorithm has correctly computed the cost to reach vertex y from s.(Keep this point in mind and you'll be able to figure out where is what going wrong!!)

Okay So now my source vertex is A.

At each step, I need to make sure that when vertex 'v' is added to set S, means it's shortest distance from source has been calculated, it must be really minimum and you should be able to verify it from the graph as well.

So, below is how the algorithm works

(1)First I start with source vertex A and relax vertex B with cost as 1. is this correct? Yes, we can see from the graph that the best cost to reach vertex b is from a with cost 1.

(2)Then I process vertex b, and it is now included in S as it's shortest path from source is determined. Now I relax all edges leaving B,and set path cost of C as 3, and path cost to e as -2. Are they correct? Is it really that to reach e from A I would have minimum cost of -2? Yes from graph it seems so.Similar is story for vertex C.

Since, the cost to reach b from source vertex a was correctly computed and found minimum, all vertices, which are reachable from vertex b also should have been correctly computed minimum cost from source vertex a.

(3)Now, e is included in set S and I relax edge to vertex f and cost comes to be 0. Is it correct? yes from the graph I can manually find that it is correct.

So you notice? At each step, we have to check that when a vertex v is included in set S, the distance to reach this vertex v from source vertex s must have been correctly determined in order for Dijkstra to work correctly.

Now Consider the scenario when source vertex is D and the algorithm is executed.

Now, consider the scenario, when vertex g was included in set S and all edges from g were relaxed.

cost to e from d changed to 3

cost to h from d changed to 4.

And both are wrong, if you see the graph.

The actual cost to reach vertex e from d (minimum) is 0 (d-a-b-e)

And to h also the correct minimum cost is 0 (d-a-b-c-h)

So, from this point onwards the trouble started.

And as you can see, vertex h is processed before vertex c and since h is processed, this means it is included in set S which means you have correctly computed the shortest path cost to reach h from d which is wrong!!. You see the fun part is, till the point finally when h is included in set S (vertices whose shortest path cost from source vertex have been determined), no one changed cost of h to correct value 0 and it got included in S with wrong cost!!.

Obviously, vertex g is responsible for this, and if C was processed before g, this could have been prevented!!.

In order to h have correct minimum path cost from d, it must have been processed after vertex C, because the minimum cost to reach C from d  is 5 and then to h it would have been 0 and this is correct!!.

–1 vote
Dijkstra's single source shortest path algorithm here this works fine bcoz there is no -ve weight cycle in graph.
+3
D is the correct option, but the explanation you have provided does not seem right.
+1
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.