Floyd Warshall
Computes the distance between all Pairs of nodes
Key ideas: Shortest path have optimal substructure
All subpath of the shortest path is the shortest path
All subpath of the shortest path is the shortest path
Dynamic Programming
1. Figure out the subproblems
2. Relate the subproblem solutions
3. Recurse and memorise
4. Solve the original problem via subproblems
Optimal Sub-structure
The optimal solution can be constructed from optimal solutions to smaller sub problems
Greedy Structure
- Dijkstra's Algorithm
- Minimum spanning tree
Divide and Conquer
- Merge sort
Overlapping subproblems
The same smaller problem is used to solve multiple bigger different problems
The idea
Let S[v,w,P] be the distance of the shortest path from v to w
that only uses intermediate nodes in the set P.
We do not have to use all the nodes in the set.
We will compute increasingly large sets.
This makes use of precalculation.
We have two choices each time
To use the original path
To go through one more node
Use the minimum of the two choice.
1. Initialised the table to all infinity
2. Fill adjacency matrix using edges
If there does not exist an edge, change to infinity
3. For every pair, look at the table an decide if
its better to go direct
or to pass through another node.
4. The Set p will only contain the nodes which must be included in graph
Function FloydWarshall(G)
S = Array of size |V|x|V| //memoization table S has |V| rows and |V| columns
// Initialize every pair of nodes O(V^2)
for v = 0 to |V|-1
for w = 0 to |V|-1
S[v,w] = E[v,w]// For sets P0, P1, P2, P3, …, for every pair (v,w)
//search for new paths O(V^3)
for k = 0 to |V|-1
for v = 0 to |V|-1
for w = 0 to |V|-1
S[v,w] = min(S[v,w], S[v,k]+S[k,w])
return S
S = Array of size |V|x|V| //memoization table S has |V| rows and |V| columns
// Initialize every pair of nodes O(V^2)
for v = 0 to |V|-1
for w = 0 to |V|-1
S[v,w] = E[v,w]// For sets P0, P1, P2, P3, …, for every pair (v,w)
//search for new paths O(V^3)
for k = 0 to |V|-1
for v = 0 to |V|-1
for w = 0 to |V|-1
S[v,w] = min(S[v,w], S[v,k]+S[k,w])
return S
The time complexity is O(v^3)
How to store the path?
- For other, we store the parent but for floydd washall we can only sotre the parent for every possible
source,
We need to store into the 2D array, in each 2D array space, will show who is connected to the parent.
We can use this method to precompute all the shortest path so that querying it will be easy.
Nearest Repeated Words Problem
Imagine we are given a text:
“I am so happy we’re getting more problems tosolve. Nothing pleases me more than solvingproblems. I love solving problems. Especially toughproblems. The harder the better! Give me moreproblems!”We want to find the most efficient algo to find the distance between the closest repeated words.
Easiest Method:
For every word, search through every word by looking through every other word and record repetition.
O(n^2)
New Idea:
As we go through the text, hash the text and store the index where we last store it. Look up the word in the hashtable and find the difference in distance.
Update and move forward.
Assume hashtable is O(1)
Look up is O(n)