Dynamic Programming Algorithms
The basic idea behind dynamic programming is the organisation of work in order to avoid repetition of work already done.
All Pairs shortest paths
Given a directed graph
G = <N,E>
where each edge has an associated 'length' (or 'cost'), find the shortest (cheapest) distance between each pair of nodes in the graph.
Note : Although we allow negative edges, we do not allow negative cycles.
Suppose the shortest path from i to j passes through k.
Then the path taken from i to k must be the shortest available. So must the path taken from k to j.
Now we define a function d(k,i,j) as
d(k,i,j) = shortest distance from i to j using only nodes 1...k as intermediate points.
If given lengths of edges are L(i,j) then
d(0,i,j) = L(i,j)
ie. use direct paths only, no intermediate nodes.
How do we calculate d(k,i,j) for k > 0 ?
We want to find the shortest path from i to j (using only 1...k as intermediates).
We have two possibilities :
- The path doesn't actually use the node k
In the first case, use only intermediate nodes 1...(k-1) and length of path is just
d(k-1,i,j)
In the second it is
d(k-1,i,k) + d(k-1,k,j)
This gives :
d(k,i,j) = min(d(k-1,i,j) , d(k-1,i,k)+d(k-1,k,j))
The easiest way to calculate this is bottom up.
This is the Floyd-Warshall algorithm.
E-mail : graham@cs.man.ac.uk