### Floyd Warshall Algorithm

__Introduction__

This algorithm runs in O(n^3) time yet it gives shortest path between any two points. The algorithms simply looks the shortest path between two nodes passing a selected node. This operation takes place by using an adjacency matrix. Where the graph is represented using a matrix. Down the rows and through the columns nodes are represented. In the matrix distances are displayed. Distances are taken from row number to columns. See the following example graph with 3 nodes

this contains edges 0-2 = 5 and 1-2 = 10 only. Such a graph will be shown as

Graph = {

{ 0 INF 5},

{INF 0 10},

{INF INF 0}

}

Here we consider Rows as the source vertex and Columns as the target vertex.

__Implementation__

The algorithm consider a vertex and calculate all the paths through it.

In a vector notation this makes more sense. Say we have a path P(a,b) path a to b. What we do in the algorithm is consider all paths P(a,c) + P(c,b) = P(a,b) until we get min(P(a,b)). This can be implemented using 3 for(;;) loops as follows. With an adjacency matrix the work is so simple. Once done taking the path between any two points becomes peanuts.

__Java Code__

Feel free to visit the entire algorithms repository, I'm updating this daily:

## Comments

## Post a Comment