The FAQ in Bellman-Ford algorithm, Dijkstra’s Algorithm, and Dynamic Programming
(A) Why the Bellman-Ford algorithm cannot handle negative weight cycled graphs as input?
Generally, the Bellman-Ford algorithm gives an accurate shortest path in (N-1) iterations where N is the number of vertexes, but if a graph has a negative weighted cycle, it will not give the accurate shortest path in (N-1) iterations. It acquires more iteration and reduces the cost, but it does not go to end. Therefore we cannot handle the negative weighted cycle by using the Bellman-Ford algorithm.
(B) What is the purpose of the priority queue in Dijkstra’s Algorithm?
The priority queue selects the next vertex so as to ensure the shortest paths in a weighted graph by adding all nodes with their distance decorations as the priority. If we use the FIFO queue instead, we cannot be able to account for the arbitrary edge weights.
(C) Key properties an optimization problem should have if the dynamic programming approach is applicable to the problem.
1. Optimal Substructure
A given problem is said to have the optimal substructure property if an optimal solution of the given problem can be obtained by using optimal solutions of its subproblems. Or we can say that a globally optimal solution can be obtained by combining its local optimal solutions.
2. Overlapping Subproblems
It happens when an algorithm revisits the same problem over and over. Unlike divide and conquer, dynamic programming store the result of a particular subproblem, and then reuse it when revisit. From this approach of dynamic programming, it runs faster compared to divide and conquer.
(D) Why greedy solutions would generally run faster compared to dynamic programming solutions.
The greedy algorithm runs through a one set of subproblems whereas dynamic programming would solve all subproblems and choose one which leads to an optimal solution. Therefore the greedy algorithm takes less time than dynamic programming.
