Floyd Warshall Algorithm

Introduction

This algorithm runs in O(n³) 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

//pastebin.com/embed_js/asfvHMXZ

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

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

Like what you read? Give Anuradha Wickramarachchi a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.