INITIALIZATION:
For i = 1 ... n {
For j = 1 ... n {
if a[i,j] = 0 then P[i,j] = infinite
// i.e. if there is no direct path then put path length as infinite
else P[i,j] =a[i,j];
}
}
ALGORITHM:
For i = 1 ... n { //i loops over the intermediate vertices
For j = 1 ... n {
For k = 1 ... n {
P[j, k] = min( p[j,k] , p[j,i] + p[i,k]);
}
}
}
Time complexity $O(n^3)$
This algorithm is for weighted graph but it will work for unweighted graph too because if $p[i,j]=1$, $p[i,k]=1$ and $p[k,j]=1$ then according to the algorithm $p[i,j] = \min(p[i,j] ,p[i,k] + p[k,j]) = \min(1,2) =1$
And all the other cases are also satisfied. $($like if $p[i,j]$ was $0$ in last iteration and there exist a path via $k)$