Editing Greedy algorithm (section)

==Applications==
{{Expand section|date=June 2018}}
Greedy algorithms typically (but not always) fail to find the globally optimal solution because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early, preventing them from finding the best overall solution later. For example, all known [[greedy coloring]] algorithms for the [[graph coloring problem]] and all other [[NP-complete]] problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like [[dynamic programming]]. Examples of such greedy algorithms are [[Kruskal's algorithm]] and [[Prim's algorithm]] for finding [[minimum spanning tree]]s and the algorithm for finding optimum [[Huffman tree]]s.

Greedy algorithms appear in network [[routing]] as well.  Using greedy routing, a message is forwarded to the neighbouring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in [[geographic routing]] used by [[ad hoc network]]s.  Location may also be an entirely artificial construct as in [[small world routing]] and [[distributed hash table]].