[NY_Entrepreneur]

One famous application of dynamic programming is finding shortest paths in directed acyclic graphs. Maybe should credit E. Dijkstra. As I recall, that is not regarded as the most efficient such algorithm, but I haven't considered that problem for years.

[eru]

As far as I know Dijkstra's algorithm is the fastest path finding algorithm in general directed graphs without cycles of negative length. But you have to employ fibonacci heaps (or so) to get the best run-time.

If you have some heuristics to guide your path finding, e.g. if you are trying to find paths on a map, then you can do better than Dijkstra's algorithm. See A*.

[eru]

P.S. There's also Bellman-Ford.