CS2040s: All Pairs Shortest Paths (APSP) + Revision

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

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  

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)

Graphs