CLICK ON THIS IMAGE

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 : 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