edited by
27,247 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

1 votes
1 votes

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.

0 votes
0 votes
Dijkstra's single source shortest path algorithm here this works fine bcoz there is no -ve weight cycle in graph.
0 votes
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

0 votes
0 votes

Node : distance, parent

Dij run gives this : 

A : 0, NIL

B : 1,a

C :3c 

D : 6c

E : -2b

F : -1e

G :2f

H :-2c

 

Which are in fact correct if you observe the graph. So, all vertices got luckily correct in this example.

Answer:

Related questions

31 votes
31 votes
6 answers
1
Kathleen asked Sep 11, 2014
35,317 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,226 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)$...