GATE CSE 2008 | Question: 45

Question

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

• A. only vertex $a$

• B. only vertices $a, e, f, g, h$

• C. only vertices $a, b, c, d$

• D. all the vertices

Comments

@yogesh88

Dijkstra will surely fail in the case of negative edge wt cycle .

---

@ASNR1010
the order of selection of edge is: 𝐚 𝐛 𝐞 𝐟 𝐠 𝐜 𝐡 𝐝

---

@Pranavpurkar Yes True iff it is reachable form source vertex

Answer 1

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.

Comments

@ASNR1010

the cost of e will become -2 when we delete b from the minheap that we used while performing dijkstra...and find the cost of e from b.(which is -3 here)...so total cost from a to e will become         1 +(- 3)= -2...so this is how cost of e will become -2.

---

Thanks. I got it..

---

Every doubt regarding Dijkstra and -ve weights will be cleared after reading @Sachin Mittal 1 Sir and @ankitgupta.1729 Sir’s comments.

 

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

Comments

@Chhotu

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

Answer 3

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)

Comments

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.

---

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.

---

Even I had the same doubt after going through the implementation given in CLRS. Then there’s another ambiguity in Sedgewick’s course videos on Coursera and his book (although the book does mention the difference). 

The different implementations might cause confusions in case of graphs containing negative weight edges. The comments and the conclusion mentioned by @pritishc is really helpful!
 

Answer 4

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.

Comments

Check if my approach is Correct :

 

1. I will first Check for neg- weight cycle. If not found then step 2.
2. Then i will apply Dijkstra algo, if algo. is fixing the distance to vertex ‘e’ or ‘h’ before visiting edge ‘b’ or ‘c’ (thus not even considering the Neg- Edges ‘b-e’ and ‘c-h’) , then i will check if a shorter distance to it was possible through ‘b’ or ‘e’, and if YES then declare that it won’t give correct answer.