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: 

url: https://github.com/anuradhawick/Algorithms