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
This table stores the shortest path from the source to each vertex using at most
Remember, shortest path always has at most
You may wonder what the heck
In the figure above,
The rest of the columns are initialized with
At each step, we incremement the number of edges allowed by
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
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)
)
)