IITD EET Interview

Question

Question was about Single Source shortest path -
We know that Dijkstra may/ may not handle negative edge weights in graph but Bellman Ford can. Also, the time complexity of bellman ford is higher than that of Dijkstra's. Now what if we add a large positive integer to all the weights of the graph, and then simply apply Dijkstra? What is the need of Bellman Ford then?

Comments

@mahima,

please make corrections in ur statement that  Dijkstra cannot handle negative edge weights cycle in the graph but Bellman-Ford can...

---

Yes Dijkstra algorithm may or may not handle negative edge weight but can never handle negative edge cycle correct if I am wrong

Answer 1

Generally adding a weight changes the length of different paths by different amount. Say one path contains 3 edges and another contains 1 edge, and you increment weight by 1, then length of first path is increased by 3 whereas length of second path is increased by only 1. Below is an example of case where adding a weight approach fails. Shortest path from leftmost node to rightmost node is shown in red.

Before:

After: