TSP
TSP can be represented as the minimum of the shortest path from a source to another target vertex plus an edge from target to source such that all vertices are visited
Chain Matrix Mult
Fill diagonally in chain length
Recurrence
using intervals from left to right
preserving input order while tackling different ways for order of operations
Edit Distance
recurrence relation is the minimum of the operation choices to get the string to look like it
2d matrix
APSP
Shortest paths (with negative weights) given a source vertex Bellman-Ford
Loop 1...n
loop every edge (u, v)
correct d(v) if incorrect (update distance map)
Incorrect means there an edge
How to compute all-pairs sp?
Johnson’s Algorithm
Feasible potential: Key idea - Triangle inequality where the weight of a vertex has to be geq to d(v) - d(u)
So johnsons’s alg fixes an arbitrary source vertex and computes d(s, v) for all vertices via Bellman-Ford Compute new weights Run djikstra’s since weights are all positive
DP solu with Floyd Warshall
use intermediate vertices
loop j = 0...n
loop every vert
loop every vert
D(u, v, j) = min(D(u, v, j - 1), D(u, v_j, j - 1) + D(v_j, v, j - 1)