Write down the algorithm for all pair shortest path.
Subject Algorithm Design
NU Year Set: 1.(c) Marks: 3 Year: 2008

he algorithm is based on dynamic programming, in which each major loop will invoke an operation that is very similar to matrix multiplication. Following the DP strategy, the structure of this problem is, for any two vertices u and v,

  1. if u=v, then the shortest path p from u to v is 0.
  2. otherwise, decompose p into u→x→v, where p' is a path from u to x and contains at most k edges and it is the shortest path from u to x.

A recursive solution for the APSP problem is defined. Let dij (k) be the minimum weight of any path from i to j that contains at most k edges.

  1. If k=0, then

    dij (0) ={ 0 if i=j ∞ if i≠j

  2. Otherwise, for k≥1, dij (k) can be computed from dij (k-1) and the adjacency matrix w.
    dij (k) =min{ dij (k-1) , min1≤l≤n { dil (k-1) + wlj }}= min1≤l≤n { dil (k-1) + wlj }
 1     n   rows [A]
 2     C  new n×n matrix
 3    for  i   1 to  n
 4             do for  j   1 to  n
 5                            do  cij   ∞
 6                                  for  k   1 to  n
 7                                           do  cij   min( cij , aik + bkj )
 .                                                    /* Here's where this algorithm */
 .                                                    /* differs from MATRIX-MULTIPLY. */
 8    return  C
Login to post your comment.