The Gateway to Computer Science Excellence
+40 votes
7.5k 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

in Algorithms by
edited by | 7.5k views
0
explain this with diagram plz

not get the point why d is correct
+1
There is no rule that Dijkstra fails only when there is -ve weight cycle, it can fail fail even if there isn't any -ve weight cycle.

So, when there are -ve weight edges, dijkstra may or may not work.

7 Answers

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

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

+1
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
+4
@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.
+2
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??
+83

@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.
+3

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

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
I m totally confused please help me out in dijkastta how negative weight exists?
0
@swati e to f distance is 2
+12

Adding 2 points to Sachin's comment :-

$1)$ Dijkstra's Algo assumes that all edge-weights are non-negative , not positive. It means if edge weight is $zero$  then it will also work correctly.

$2)$ Re-weighting may change the shortest path , means if we add a constant to each edge weight then shortest path from a source vertex to a given vertex can be changed.So, adding a constant to each edge-weight does not work here.

So, if we apply Dijkstra's algo in case of negative edge-weights and get the wrong answer. Now if we think that after re-weighting , we get the right answer , then it will be wrong because re-weighting may change the actual shortest path.

For example , PFA ! (here after re-weighting , actual shortest path changed from $A\rightarrow B\rightarrow D\rightarrow C$ to $A\rightarrow C$ )

0
@ankit

in this question, if we calculate some distance from a to h

then a-b-c-h is correct path, though it is -ve

but, a-b-c-d-g-h is not correct path

then how D) will be correct answer?
0
@ankit, @Sachin

in both of ur example , if we run dijkstra

in 1st step , it will not give correct shortest path, I agree.

But if it proceeds further steps , this -ve weight edges also give correct shortest path.

right?
0
@srestha , In the given question , if we consider source node as 'a' and if we have to find the shortest  path from 'a' to 'h' then Dijkstra's algo will give the correct shortest path from 'a' to 'h' as $a\rightarrow b\rightarrow c\rightarrow h$ as you said with shortest path length of $-2$. $a\rightarrow b\rightarrow c\rightarrow d\rightarrow g\rightarrow h$ is not the correct shortest path and Dijkstra's algo will also not give this path.

In the example which I have shown, if we apply Dijkstra's algo then  shortest path from $A\rightarrow C$ will be the direct edge of $A\rightarrow C$ only with path length of $2$. Because if we use min-heap data structure in Dijkstra's algo to store info about nodes. Then initially for 'A' , $d[u]=0$ and $d[u] = \infty$ for all other nodes. Now in first iteration , we remove 'a' and after relaxation of edges , for C ,$d[u]=2$ and parent pointer will be from $A$ and and for B ,  $d[u]=3$. Since , 2 is minimum , so we pick vertex $C$ and delete it from min-heap . So, now using parent pointer we will reach $C$  from $A$. So, shortest path from $A$ to $C$ using Dijkstra's algo will be $2$ here which is actually incorrect.
0

@ankit

that is not a problem of -ve edge weight

It is problem of directed graph and also ur final destination

See in this question all edges are +ve, Still if it give correct shortest path it will be SBDT i.e. 10

https://gateoverflow.in/1765/gate2012-40?fbclid=IwAR1OSI3KvIrjUjxCF9EEujhDXznKsrmbqCJU-oFTVi-Bj6ohYH6DgoaIy_M

right?

+1
@srestha , From $S$ to $T$ , shortest paths are $SDT$ , $SBDT$ , $SACET$ which all are of length $10$ but Dijkstra's algo will give shortest path from $S$ to $T$ as $SACET$.
0
then conclusion is Dijkstra not finding shortest path for some cases which may or maynot contain -ve weight edges

rt?

Then how in this question , how D) will be answer.

how we can say, it is giving correct result for all edges??
+3

@srestha

$1)$ If a graph contains negative weight edge(s) then Dijkstra's algo may or may not give the correct shortest path from source vertex to all the other vertices.

In the given question , Dijkstra's algo is giving shortest path from source vertex to all other vertices but the examples which sachin and I have shown , It is not giving the correct shortest path from source vertex to some other vertex(in my example , it is vertex $C)$.

 

$2)$ If a graph contains negative weight cycle  then for those vertices which are reachable from source vertex and going through negative weight cycle then it is impossible to find the correct shortest path from Dijkstra or any other algo because after every iteration in the loop, total negative edge weights will be decremented each time. So, it will be impossible to find the correct shortest path in that case. But if a vertex is reachable from source vertex and not going through the negative weight  cycle then we can always find the correct shortest path for that vertex even if the negative weight cycle present in the graph.

For example  

Here , in this graph , suppose source vertex is $A$. Then  shortest path from $A$ to $F$ will always be of length 1 which is the direct edge from $A$ to $F$ using Dijkstra's algo.

But we can't find the correct shortest path from $A$ to $B$ using Dijkstra's algo because it is impossible to find. Like $2$ then $2+3+4+(-8)$ then $2+3+4+(-8) + 3+4+(-8)$ ... so on.

0

what about positive edge weight?

But if a vertex is reachable from source vertex and not going through the negative weight  cycle then we can always find the correct shortest path for that vertex even if the negative weight cycle present in the graph.

this is wrong

because in 2012 question, there is even positive edge weight, still it is not shortest path of the graph 

0
in that gate 2012 question, SACET is the correct shortest path from  vertex $S$ to $T$ using Dijkstra's algo and the assumption which is given in the question. right ?
+3 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. 

by
0

@Chhotu

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

+3 votes

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

So here answer is (D)

by
0
how r u getting g to e=3

Source is d

right?
0
@srestha-You mean cost to reach vertex e from d when parent of e in such path is g=3?
Yes source is d
0

I tried running Dijkstra using source node $d$, but did not run into the alleged trouble that I should have according to the above.

$c$ is the last node to be processed out of all of them, but when it is processed, it relaxes $h.key$ to $0$. I did not follow any tabular method as given above, but just ran the algorithm given in Cormen line by line.

This is what the predecessor subgraph looks like for this run of Dijkstra -:

It is true that initially $h.key$ is relaxed to $4$, but it is rectified in the later step. Even though $h$ does not exist in the priority queue at the time of $c$ relaxing it.

+1

In @Sachin Mittal 1's example on the selected answer though, I did run into trouble. With source $A$, $D.key$ is relaxed once to $2 + 3 = 5$ via $A - C - D$ and never touched again. But $C.key$ is first relaxed to $2$, and then to $1$. This results in the wrong picture.

Conclusion -:

  • Dijkstra works in all cases where the edge weights are only non-negative.
  • Dijkstra may or may not work in cases where negative weight edges are present.
  • In the negative weight edge cases where it works, a negative weight cycle, if any present, should not be reachable from the source.

https://cs.stackexchange.com/questions/19771/why-does-dijkstras-algorithm-fail-on-a-negative-weighted-graphs

Dijkstra is ultimately a greedy algorithm that makes locally optimal decisions at every step. If edge weights are non-negative, then locally optimal decisions lead to globally optimal consequence (can't relax edge weights further, which you can do in Sachin's example, which causes the problem). If they can be negative, then local optimality may not always be correct.

+1 vote

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.

by
+1 vote

Dijkstra's algorithm may not give you desired results when:-

  1. Graph is disconnected.
  2. There are negative weights.

#1

If a graph is disconnected, a vertex, say v can't reach some vertex, say w. If we can't even reach w from v, there's no question of calculating the shortest distance to reach w from v.

Hence, Dijkstra will definitely cause issues when v is the source.


#2.1

Let's see what happens when we have a negative weight cycle.

Suppose the cycle altogether gives you $-5$ weight.

Take the cycle once, weight reduces by 5. Take the cycle again, weight reduces by 5 again. You can keep taking the cycle over and over and end up with a smaller number.

This cycle would lure you to $- ∞$ — which is the correct answer for the shortest path — which, in turn, won't be returned by Dijkstra's algorithm.


#2.2

If a heavier edge hides a negative edge behind it, then Dijkstra can fail again. See this for example:

Source: https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm/6799344#6799344

Dijkstra would fix the distance of A to B as $1$.

But the actual shortest distance is $-201$

 

So, negative edges are generally troublesome, and we avoid them altogether in Dijkstra.


However, in a specific case whether or not the negative edges generate correct results, depend on the specific instance.

Evidently here, Option D is correct.

by
edited by
0 votes

Dijkstra Algorithm fails for negative-edge-weight-cycle, but, here there is no negative-edge-weight cycle. So, it computes shortest path distance to all vertices. Ans: D

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

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
52,345 questions
60,468 answers
201,792 comments
95,271 users