Graphs and Dynamic Programming

In this section, we have discussed advanced graph algorithms and DP as distinctly different topics, but as is often the case, they can be used concurrently depending on the type of problem we are trying to solve and the nature of the graph. Several problems commonly associated with graphs are identified as NP-complete (graph coloring and the vertex cover problem, to name two examples) and can, under the right circumstances, be solved with dynamic programming. However, most of these topics are outside the scope of this book (and are actually worthy of having entire books dedicated specifically to their analysis).

However, one problem in graph theory is particularly well suited to the DP approach, and fortunately, it is one we are already very familiar with: the shortest-path problem. In fact, in Chapter 7, Graph Algorithms II, we actually discussed an algorithm that's commonly categorized under the DP umbrella, despite the fact that we never identified it...