The Floyd-Warshall algorithm is an O(|V|^3) algorithm for computing all-pairs shortest paths in a directed weighted graph.
During the work of Floyd–Warshall algorithm all possible paths through the directed weighted graph between each pair of vertices are compared. The complexity is O(n^3) where n is a number of vertices.
Minimal pseudo code to get only shortest paths of a graph:
for k = 1 to n
for i = 1 to n
for j = 1 to n
W[i][j] = min(W[i][j], W[i][k] + W[k][j])
Where W is a matrix (size n x n) which stores all shortest paths.
At the start W is filled with infinity (any large number which exceeds the sum of weights of a graph). For each edge (u,v) of a graph the weight of the edge (u,v) has to be placed to the matrix W.
Algorithm is allowed path reconstruction.
This algorithm is effective for full-packed graph especially stored as connectivity matrix.
