All Pairs Shortest Paths - Floyd Warshall Algorithm

Learning Resource: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Short Description:
1) This algorithm finds shortest distance been every pair of nodes in a graph.
2) The implementation shared here uses adjacency matrix representation.
3) Complexity of the algorithm is O(n^3)

Working:
1) Initialize all distances between nodes (i,j) to INF (a very large value which is guaranteed to be more than the maximum distance between two nodes - here it is chosen as 10^9) where i != j and 0 where i==j.
2) Input the distances for every node (i,j) and populate the adjacency matrix.
3) Calculate all-pairs shortest paths by iterating for all i,j,k and using the result min-distance(i,j) = min(min-distance(i,j) , min-distance(i,k)+min-distance(k,j))

Implementation:

// Nodes are numbered from 1 to n
for(int i=1; i<=n; i++)
    for(int j=1;j<=n;j++)
        a[i][j]=(i==j)?(0):(1000000000);

// Input a[][] here.

for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1;j<=n;j++)
            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);