Warshalls Algorithm

  • Warshall’s Algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles, see below) and also for finding transitive closure of a relation R.
  • Floyd-Warshall algorithm uses a matrix of lengths D0 as its input. If there is an edge between nodes i and j, than the matrix D0 contains its length at the corresponding coordinates.
  • The diagonal of the matrix contains only zeros. If there is no edge between edges i and j, than the position (i,j) contains positive infinity.
  • In other words, the matrix represents lengths of all paths between nodes that does not contain any intermediate node.
  • In each iteration of Floyd-Warshall algorithm is this matrix recalculated, so it contains lengths of paths among all pairs of nodes using gradually enlarging set of intermediate nodes.
  • The matrix D1, which is created by the first iteration of the procedure, contains paths among all nodes using exactly one (predefined) intermediate node. D2 contains lengths using two predefined intermediate nodes. Finally the matrix Dn uses n intermediate nodes.

Algorithm

Step 1: [INITIALIZE the Path Matrix] Repeat Step 2 for I= to n-1, wheren is the number of nodes in the graph
Step 2: Repeat Step 3 for J=0 to n-1 
Step 3:       IF A[I][J] = , then SET P[I][J] = 0 
              ELSE P[I][J]=1 
           [END OF LOOP] 
        [END OF LOOP]
Step 4: [Calculate the path matrix P] Repeat Step 5 for K=0 to n-1 
Step 5: Repeat Step 6 for I=0 to n-1 
Step 6: Repeat Step 7 for J= to n-1 
Step 7: SET PK [I][J]= PK-1 [I][J] V (PK-1 [I][K] A PK-1 [K][J]) 
Step 8: EXIT