KEMBAR78
Greedy Algorithms | PDF
Scribd
Upload
113 views2 pages

Greedy Algorithms

This document discusses several greedy algorithms: 1) The knapsack problem algorithm uses a greedy approach of selecting the most valuable remaining item that fits in the knapsack until it is full. 2) The activity selection algorithm greedily selects non-conflicting activities based on their start and finish times to maximize the number selected. 3) Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a graph by greedily selecting the neighbor with the lowest distance. 4) Kruskal's algorithm builds a minimum spanning tree by greedily selecting the shortest edge that does not create a cycle. 5) Prim's algorithm also builds a minimum spanning tree but does so

Uploaded by

palak
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
113 views2 pages

Greedy Algorithms

This document discusses several greedy algorithms: 1) The knapsack problem algorithm uses a greedy approach of selecting the most valuable remaining item that fits in the knapsack until it is full. 2) The activity selection algorithm greedily selects non-conflicting activities based on their start and finish times to maximize the number selected. 3) Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a graph by greedily selecting the neighbor with the lowest distance. 4) Kruskal's algorithm builds a minimum spanning tree by greedily selecting the shortest edge that does not create a cycle. 5) Prim's algorithm also builds a minimum spanning tree but does so

Uploaded by

palak
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Greedy Algorithms

11.Greedy Algorithm : Knapsack ( W[1..n],V[1,..n], W)


{initialization }
for i  1 to n do X[i] =0.
weight  0.
{ greedy loop }
while weight < W do
i the best remaining object
if weight + W[i] ≤ W then X[i]  1.
weight  weight + W[i]
else
X[i]  ( W – weight )/ W[i]
weight  W.
return X
12.Algorithm : Greedy-ActivitySelection (s, f)
n length (S)
A  {a }
1

i 1
for m  2 to n
do if S ≥ f
m i

then A  A U {a }
m

i m
return A.

13.Algorithm Dijkstra ( L[1…n,1….n], D [2…n])


{ initialization }
C {2,3,…..n} { S= N\C exists only implicitly}
for 1 2 to n do
D[i]  L[1,i]
{ greedy loop }
v some element of C minimizing D[v]
C  C \ {v} { and implicitly S  S U {v} }
for each w ϵ C do
D[w]  min (D[w], D[v] +L[v, w]
return D.
14.Algorithm Kruskal ( G= (N,A) : set of edges)
{ initialization }
Sort A by increasing length.
n the number of nodes in N
T ϕ { will contain the edges of MST }
initialize n sets, each containing a different element of N.
{ greedy loop }
repeat
e {u,v} : shortest edge not yet considered.
ucomp  find(u)
vcomp  find(v)
if ucomp ≠ vcomp then merge (ucomp, vcomp )
T  T U {e }
until T contains n-1 edges
return T.

15. Algorithm Prim’s ( G= (N,A) : set of edges)


{ initialization }
T ϕ { will contain the edges of MST }
B  { an arbitrary member of N}
{ greedy loop }
while B ≠ N do
find e {u,v} of minimum length such that
u ϵ B and v ϵ N \ B
T  T U {e }
B  B U {v }
return T.

You might also like