Let’s start talking about Floyd’s algorithm for the APSP
I think of Floyd’s Algorithm as a combination of three ideas.
Copyright By PowCoder代写 加微信 powcoder
Great idea #1: number the vertices of the graph 1, 2, 3, …, n
Why? So that we have a way to refer to vertices in some order.
Notice: there’s no vertex numbered 0
Great idea #2: restricting the allowed intermediate vertices on a path
In Floyd’s algorithm, we use k to denote the allowed intermediate vertices on the paths.
i.e. the allowed intermediate vertices on a path are {1, 2, 3, …, k}
Sample graph:
1->10[weight 50]
1->9[weight 2]
9->10[weight 1]
Shortest path from 1 to 10 is 3. 1->9->10
Floyd would allow this path if k >= 9.
What’s the shortest path from 1 to 10 if k is 0? 50. 1->10
What if k is 1?? still 50
What if k is 8? still 50
Floyd goes like this:
-solve it for k = 0
-solve it for k = 1, using the k = 0 solutions
-… keep going, k = 2, k = 3, … k = n
When k is n, it means that we can have {1, 2, 3, …, n} as intermediate vertices; aka no restriction on our paths.
Great idea #3: a shortest path consists of two “smaller” shortest paths.
Let P be the shortest path that starts at u, ends at v, and whose intermediate vertices are in {1, 2, …, k}
Claim: P has no cycles.
Why? Suppose P did have a cycle. You can remove the cycle and get a shorter path than P (contradiction).
This relies on our assumption that the graph has no negative cycles.
Let’s assume that P uses vertex k somewhere.
Here’s what P looks like
u->…..->k->…..->v
So we can decompose this path P into two paths, like this:
-P starts at u.
-Then it has a path p1 from u to k
-then it has a path p2 from k to v
Talk to me about p1:
p1 starts at u
p1 ends at k
What are the intermediate vertices on p1? They’re from the set {1, 2, …, k-1}. No k!
Let’s save base cases, k = 0, for later.
For now, think of k as a big number.
Let A be our dynamic programming table.
a[k][i][j]: shortest path starting at vertex i, ending at vertex j, and allowed to use {1, 2, …, k} as intermediate vertices
a[k][i][j] = min(
// Option 1: maybe the shortest path doesn’t use k at all
A[k-1][u][v],
// Option 2: the shortest path does use vertex k as an intermediate vertex
A[k-1][u][k] + A[k-1][k][v])
// this is shortest path from u to k + shortest path from k to v = shortest path from u to v
Now let’s think about base cases.
aka A[0][…][…]; k is 0
A[0, u, u] = 0
This is not allowed in our graph: u->u[weight -100]
a[0, u, v] = (for u != v)
infinity, if there is no edge u->v
w(u, v) if there is edge u->v
———-
LPS = longest palindromic subsequence
AABCBABBCA
What’s the LPS here?
What are some easy problems we can solve?
I’m noticing that, regardless of where the subproblems are in the string, they’re easy if they have only one character. The answer for a one-character substring is 1.
AABCBABBCA
Notice here that the first and last characters are the same.
Claim: the LPS has to include these two characters.
A [solve ABCBABBC] A
Now I have to find the LPS of a smaller string.
This smaller string has a different starting index and a different ending index than the original string.
opt[i][j] = LPS of string from index i to index j
if s[i] == s[j]:
opt[i][j] = 2 + opt[i+1][j-1]
With only one array dimension, we wouldn’t be able to keep track of both our current starting point and ending point.
OK — so we know what to do if s[i] == s[j]. It’s 2 + LPS of rest of string.
Let’s imagine a different string where the first and last characters are not equal.
We cannot include both the x at the beginning and the y at the end.
So our options are:
1. [eliminated] use x at beginning and y at end
2. don’t use x at beginning
opt[i][j] = opt[i+1][j]
3. don’t use y at the end
opt[i][j] = opt[i][j – 1]
4. don’t use x at beginning and don’t use y at end
opt[i][j] = opt[i+1][j-1]
<-- not needed though because this option can be accomplished by using option 2 and then option 3.
Base cases:
for i in range(len(s)):
opt[i][i] = 1
When we're not in the base case:
suppose we're inside the i and j loops.
if s[i] == s[j]:
opt[i][j] = 2 + opt[i+1][j-1]
opt[i][j] = max(opt[i+1][j], opt[i][j-1])
If you want to use memoization instead of bottom-up dynamic programming, you have what you need now.
If you want the bottom-up code, you need the right order to solve the subproblems.
In activity scheduling and knapsack, we did increasing i.
for i in range(n):
but here, to solve opt[i][j], we need opt[i+1][...]
So we can't solve these in order of increasing i.
if s[i] == s[j]:
opt[i][j] = 2 + opt[i+1][j-1]
opt[i][j] = max(opt[i+1][j], opt[i][j-1])
for i in [n-1, n-2, ..., 1, 0]:
for j in [i+1, i+2, i+3, ..., n-1]:
There's another way to fill out this table...
When trying to solve [i][j], you need [i+1][j-1], [i+1][j], and [i][j-1]
All of the subproblems are on strings that are smaller length than s[i]...s[j]
Fill out the table in increasing order of string size.
First, all strings of length 1 (base cases):
opt[0][0], opt[1][1], opt[2][2], opt[3][3]
Then all strings of length 2:
opt[0][1], opt[1][2], opt[2][3], opt[3][4]...
Then all strings of length 3:
opt[0][2], opt[1][3], opt[2][4], ...