Greedy Method
G A Vijayalakshmi Pai · 2022
This chapter discusses the greedy method and demonstrates the strategy over the Knapsack problem , Prim's and Kruskal's spanning tree extraction algorithms and Dijkstra's Single Source Shortest Path problem . The greedy method proceeds to obtain the feasible and optimal solution, by considering the inputs one at a time. A greedy solution to the knapsack problem involves selecting the objects one by one such that the addition of each object into the knapsack increases the profit value, subject to the capacity of the knapsack. Kruskal's algorithm selects a minimum cost edge one by one, just as Prim's algorithm does, but with a huge difference in that, the selected edges build a forest and not necessarily a tree, during the construction. Dijkstra's algorithm obtains an elegant solution to the single source shortest path problem.