726 views
1 votes
1 votes

If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop 

  1. TRUE
  2. FALSE

1 Answer

0 votes
0 votes
False. Dijkstra's algorithm is a single-source shortest path algorithm that finds the shortest path from a source vertex to all other vertices in a graph. It uses a priority queue to select the next vertex to visit and update the distances of its neighbors. Dijkstra's algorithm does not consider negative weight edges, so it is not affected by the presence of negative weight cycles in the graph. If a negative weight cycle is reachable from the source vertex, Dijkstra's algorithm will simply ignore it and continue executing as normal.

Related questions

0 votes
0 votes
0 answers
2
6 votes
6 votes
1 answer
3
vaishali jhalani asked Nov 5, 2016
3,054 views
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?
1 votes
1 votes
1 answer
4
vaishali jhalani asked Nov 4, 2016
1,079 views
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?