ABSTRACT
Finding a best alignment between DNA sequences and finding a desirable routing using a GPS system can be accomplished by determining shortest paths in an associated table or graph. Solutions to both of these problems can be approached by invoking the dynamic programming principle introduced in Chapter 2. Namely, we optimally solve certain smaller subproblems along the way to solving optimally the original problem. In particular, we introduce Dijkstra’s Algorithm, a greedy-type approach that is nonetheless guaranteed to produce an optimal path in a weighted graph.
