Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms

Question

From my understanding, a problem amenable to a dynamic programming solution has these two properties:

1. Overlapping Subproblems — The same subcase (a subsection of the overall problem) keeps reappearing. Thus, memoization can be used to boost performance.
2. Optimal Substructure — The problem can be broken down into smaller components, which can then be solved independently and the results combined to produce the answer to the overall problem. This allows for subproblems and possibly overlapping subproblems.

I've read that Bellman-Ford and Floyd-Warshall are dynamic programming algorithms, but how do I think of them in terms of the two properties given above?

Answer 1

Floyd–Warshall algorithm

You can prove inductively that on the $k$th iteration, the algorithm computes, for each pair of vertices $i,j$, the shortest path between $i$ and $j$ that passes through the vertices $1,\ldots,k$. How does it do that? When $k = 0$, you can read this off the adjacency matrix. For larger $k$, there are two possibilities:

1. The shortest path from $i$ to $j$ through $1,\ldots,k$ doesn't use $k$. In this case it equals the shortest path from $i$ to $j$ through $1,\ldots,k-1$.

2. The shortest path does use $k$. In this case you can break it up to two parts: a part from $i$ to $k$, and a part from $k$ to $j$. In both parts, the path only goes through $1,\ldots,k-1$.

You can therefore compute the shortest past from $i$ to $j$ through $1,\ldots,k$ using shortest paths that go through $1,\ldots,k-1$. Taking $k = n$, we obtain the unrestricted shortest paths.

Bellman–Ford algorithm

Let us consider first a parallel version of the Bellman–Ford algorithm which updates all weights simultaneously. In this case, you can show that on the $k$th iteration, the algorithm computes, for each pair of vertices $i,j$, the shortest path between $i$ and $j$ that is of length at most $k$. When $k = 1$, this is easy. For larger $k$, there are two possibilities:

1. The shortest path of length at most $k$ actually has length at most $k-1$.

2. The shortest path of length at most $k$ has length exactly $k$. Let $v$ be the penultimate vertex in one such path. Then the length of shortest path from $i$ to $j$ of length at most $k$ is the length of the shortest path from $i$ to $v$ of length at most $k-1$, plus the length of the edge from $v$ to $j$.

Once again, this can be computed by induction on $k$. Taking $k = n-1$, we obtain the unrestricted shortest paths (assuming no negative cycles).

The usual algorithm, which is sequential, is a bit different, but you can show that it is at least as good as the parallel algorithm.