Dynamic Programming
Dynamic programming is a method often used to solve optimization problems that require searching through a space of possible solutions.
Table of contents
Comparison with Divide and Conquer
Divide and Conquer methods often provide a simple and intuitive solution to problems, by dividing the problem into smaller subproblems and then combining the solutions to the subproblems.
However, for some questions divide and conquer may be inefficient if they solve the same subproblems over and over again.
In dynamic programming, we solve each subproblem only once and store the solution in a table, and when the same subproblem occurs, we just look up the solution in the table.
Bellman-Ford Algorithm
A bottom-up dynamic programming algorithm.
Bellman-Ford algorithm is a single-source shortest path algorithm.
Review the non-DP version of the algorithm in the link above.
In Bellman-Ford DP, we maintain a table of size $|V| \times |V|$.
This table stores the shortest path from the source to each vertex using at most $k$ edges ($0$ to $|V| - 1$).
Remember, shortest path always has at most $|V| - 1$ edges, because it is a tree.
You may wonder what the heck $0$ edges is doing there, because obviously we can’t go anywhere with $0$ edges. But because DP is inductive, it is necessary to have a base case (and your code gets ugly if you don’t).
In the figure above, $v_0$ is the source vertex. Regardless of the number of edges, you can get to itself with a weight of $0$, so the entire column can be initialized with $0$.
The rest of the columns are initialized with $\infty$.
At each step, we incremement the number of edges allowed by $1$, (go down a row in the table) and go through each vertex $v$ while looking at the row above it to see if we can find a shorter path by using one more edge.
If an improvement is not possible, we decide not to use another edge and copy the previous row for that vertex.
We can always skip the source vertex at each step, because we already found the shortest path to itself.
So we need loops that go over $|V| - 2$ allowed edges (excluding zero) and $|V| - 1$ vertices (excluding the source).
Psuedocode:
def bf_dp(G, s):
n = len(G.V)
M = [
[0 if i == s else float('inf') for i in range(n)]
for _ in range(n)
]
for k in range(1, n-1):
for v in range(1, n):
M[k][v] = min(
M[k-1][v],
min(
M[k-1][u] + w(u, v)
for u in G.incoming_neighbor(v)
)
)