edited by
27,250 views
63 votes
63 votes

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

edited by

11 Answers

Best answer
55 votes
55 votes
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
8 votes
8 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. 

5 votes
5 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)

4 votes
4 votes

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.

edited by
Answer:

Related questions

31 votes
31 votes
6 answers
1
Kathleen asked Sep 11, 2014
35,327 views
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is:$\text{MNOPQR}$...
28 votes
28 votes
6 answers
2
Kathleen asked Sep 11, 2014
13,235 views
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity$\Theta(n)$$\Theta(m)$...