### graph apsp floyd warshall

#######################################
####    all pairs shortest path    ####
#######################################

often we want to know the shortest path length for all pairs in G(V,E).

#################################
####   Floyd Warshall algo   ####
#################################

##
## input:
##

a 'directed' & 'weighted' graph G = (E,V)

only 'positive'(above zero) weight allowed for edges.

##
## output:
##

dist[][] : the shortest path length for every pair of vertices.

e.g.
dist[u][v] = the shortest path length for between u and v.
if dist[u][v] = infinity, then no path exists between them.
dist[u][u] = 0

pred[u][v] : immediate predesessor of v in dist[u][v]
(this is optional)

##
## logic flow
##

leverages dynamic programming (effective for optimal substructure and overlapping subproblems)

(ref)
algorithms in a nutshell by Heineman et al

------------------------------------------------ // pseudo code (modified from Heineman book)

foreach u (V)  // init loop
{
foreach v (V)
{
dist[u][v] = inf;
pred[u][v] = -1;   // as usual, lets call this a design
}
dist[u][u] = 0;
foreach v (immediate neighbors of u)
{
dist[u][v] = w(u,v);
pred[u][v] = u;
}
}

foreach t (V)
foreach u (V)
foreach v (V)
{
len = dist[u][t] + dist[t][v];
if( len < dist[u][v])
{
dist[u][v] = len;
pred[u][v] = pred[t][v];
}
}

--------------------------------------------------

##
##  complexity of floyd warshall:
##

--- time complexity

initialization : O(V^2 + E)
dynamic programming : O(V^3)

thus in total : O(V^3)

--- space complexity

dist[][] is a n-by-n matrix where n is the number of vertices. thus O(V^2)

##
## proof of correctness
##

proof by induction

(ref)
p.165 algorithms in a nutshell by Heineman et al
http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part3.pdf

induction hypothesis:
let V = {v1, v2,,, vk,,, vn}
after k'th iteration, dist[i][j] = the shortest distance from i to j that may go thru only {v1, v2,,, vk} in addition to vi & vj

proof;

base case(k=1) is trivial.
first iteration looks at v1 as the Mr. intermediate vertex vk.
(after initialization, if there is an edge between i-j, then dist[i][j] != infinity)
(similarly, if direct an edge exists for i-v1 v1-j pairs, after initialization, we should see finite values for dist[i][v1] and dist[v1][j])
(but that "finiteness" doesn't really matter)
so we take  dist[i][j] = min(dist[i][j] , dist[i][v1] + dist[v1][j])

===> notice in min(A,B), both A & B are data from 0th iteration, i.e., initialization

at the (k+1)th iteration, dist[i][j] = Q = (we want to show) =  the shortest distance from i to j that may go thru only {v1, v2,,, v(k+1)} in addition to vi & vj
two cases;
(a): Q does not contain v(k+1)
(b): Q contains v(k+1)

for (a), then dist[i][j] remains as the shortest distance given from the kth iteration.
for (b), then dist[i][j] is updated with  dist[i][v(k+1)] + dist[v(k+1)][j]
now notice both dist[i][v(k+1)] and dist[v(k+1)][j] are, per our induction hypothesis, guaranteed to be the shortest distance for i-to-v(k+1) and v(k+1)-to-j respectively from previous iteration = the kth iteration.
to make it more explicit, lets write it as below, and now compare the below two sentences to the induction hypothesis.
dist[i][v(k+1)] = the shortest distance from i to v(k+1) that may go thru {v1, v2,,, vk} in addition to vi & v(k+1)
dist[v(k+1)][j] = the shortest distance from i to v(k+1) that may go thru {v1, v2,,, vk} in addition to vj & v(k+1)

thus, induction hypothesis is proved correct. thus, after nth iteration, we get all pair shortest path for G
i.e.  dist[i][j] gives the shortest distance that may go thru {v1, v2,,, vn} in addition to vi & vj
note# V = {v1, v2,,, vn} is the complete V pool that includes vi & vj in this case.

#############################################
##   constructing the path from pred[][]   ##
#############################################

this is awfully simple. see how pref[][] is constructed from the above code.

e.g.  shortest path from u to v

u - a - b - c - v

pred[u][v] = c
pred[u][c] = b
pred[u][b] = a
pred[u][a] = u

now, for below psuedo code, lets get a path from vertex s to vertex t

----------------------------- // psuedo code

Stack stack;
stack.put(t);

while(t != s)

t = pred[s][t];
if(t == -1)
throw "no path";
stack.put(t);

-----------------------------

1. 2014-08-14 03:00:03 |
2. Category : algo
3. Page View: