5.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 | 5.3k views
0
explain this with diagram plz

not get the point why d is correct
0
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.

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

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?

0
@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??
0

@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

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 ?

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?

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

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

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

1
2