GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 9

Answer 1

• A. False.
  It always terminates after $\text{|E|}$ relaxations and $\text{|V| + |E|}$ priority queue operations, but may produce incorrect results.
  
  Source:  https://courses.csail.mit.edu/6.006/oldquizzes/solutions/quiz2-s2011-sol.pdf
   
• B. True. Both algorithms are guaranteed to produce the same shortest-path weight, but if there are multiple shortest paths, Dijkstra's will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.
  
  Source:  https://courses.csail.mit.edu/6.006/oldquizzes/solutions/quiz2-s2011-sol.pdf
   
• C. False. Bellman-Ford detects negative-weight directed cycles in its input graph if the cycle is reachable from the source.
  
  Source:  https://courses.csail.mit.edu/6.006/oldquizzes/solutions/final-s2008-sol-1.pdf
  
   
• D. False. Bellman-Ford requires $\Theta\text{(VE)}$, regardless of the edge weights. Dijkstra runs in $\Theta(\text{E + V} \lg \text{V})$. Because the graph is connected, $\text{E}=\Omega\text{(V)}$, so $\Theta\text{(VE)}=\Omega\left(\text{V}^2\right)$, which is clearly worse than Dijkstra.

  
  Source: https://courses.csail.mit.edu/6.006/oldquizzes/solutions/final-s2009-sol.pdf

Comments

In dikstra Algorithm a single node can be pushed mutiple times as long as it gives new decreased relaxation weight. So with negative edges it's possible that relaxation always decrease and dikstra algorithm may not terminate.

In the algorithm we won't count how many operations we performed on heap. we just continue the loop as long as the relaxations are decrease.
(src of dikstra algorithm using heapq:- https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/ )

---

For negative cycle dijkstra will run infinitely and won't terminate, since weight keeps on decreasing above guy is correct.

---

totally disagreed, Dijkstra's algorithm will always terminate because it processes each node at most once using a priority queue, ensuring a finite number of operations. However, its results may be incorrect for graphs with negative weight edges.

---

@GO Classes pls correct this