Question

Bellman-Ford and Dijkstra's algorithms solve the single-source shortest path (SSSP) problem. Explain the circumstances when you would use each of these algorithms.   

Answer 1

Both dijkstra's and Bellman-ford algorithm is used for single source shortest path problem.But there are some conditions to apply these algorithms for finding single source shortest path.

1. Dijkstra's algorithm can not apply for the graphs which contains "Negative edge weight cycle", but Bellman ford algorithm has capability to find out whether there exist negative edge weight cycle in graph or not.

2. Many people understand that dijkstra's algorithm not worked for negative edge weight but it is false. Dijktra's algorithm gives right answer for negative edge weight graphs but the condition is that it does not contain negative edge weight cycles.

3. In genral if a graph contains "n" vertices than we can find out shortest path contains "n-1" edges, this is the idea behind bellman ford algorithm. In this algorithm we apply one more time "relax" operations if any node satisfy this relax operation then we acn say that the graph contains negative edge weight cycle.

4. Greedy approach is taken to implement the dijkstra's algorithm while bellman ford uses dynamic apprach.