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) 
 
allPairsShortestPath(G) 

   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) 
http://www.imada.sdu.dk/~jbj/DM85/lec6a.pdf 
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:

Google Ads