We discuss search. minimal path and minimal spanning tree algorithms and th
eir applications to disordered systems. Greedy algorithms solve these probl
ems exactly, and are related to extremal dynamics in physics. Minimal cost
path (Dijkstra) and minimal cost spanning tree (Prim) algorithms provide ex
tremal dynamics for a polymer in a random medium (the KPZ universality clas
s) and invasion percolation (without trapping) respectively. (C) 1994 Elsev
ier Science B.V. All rights reserved.