Which of the following algorithm is not a Greedy algorithm?
Optym technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Which of the following algorithm is not a Greedy algorithm?
Show answer & explanation
Answer: D. D) Bellmen Ford Shortest path algorithm
The Bellman-Ford shortest path algorithm is based on dynamic programming (relaxing all edges |V|-1 times), whereas Dijkstra, Kruskal, and Fractional Knapsack are greedy algorithms.
Step-by-step Derivation:
Step 1: Dijkstra, Kruskal, and Fractional Knapsack make locally optimal greedy choices at each step.
Step 2: Bellman-Ford relaxes all edges systematically and handles negative weights using a dynamic programming recurrence: d[v] = min(d[v], d[u] + w(u, v)).
Step 3: Therefore, Bellman-Ford is not a greedy algorithm.