Learning About the Graph Construct using Games, Part II - Floyd-Warshall algorithm

(Page 4 of 5 )

The Floyd-Warshall algorithm finds the shortest path from every node in the graph to every node. It is a little more complicated than Dijkstra's algorithm. Here is a quick overview of how it works.

Preparation step:

The algorithm uses a two-dimensional array to hold the shortest distance between each pair of nodes. The dimensions of this array are n*n, where n is the number of nodes in the graph.

Initially, the array is filled with the edge weight of the edges between these nodes. If no edge exists between two specific nodes, a very large number is put there instead. The diagonal is filled with zeroes. You might have noticed that this is actually the adjacency matrix representation of the graph. 

The algorithm also uses another two dimensional array of the same size. The second array holds, for every pair of nodes i and j, the node immediately previous to j in the path from i to j (the same concept that was used in the previous array in Dijkstra's algorithm). Initially, it is initialized such that row number i is filled with i's.

Algorithm steps:

1. Start at node i=1
   
   
2. For every possible pair of nodes A and B
   
   
3. Increase i by 1 (consider next node). Go back to 2

Now, that wasn't easy! Was it? Let's see an example of this algorithm in action to get a real idea of how it works.

First, let's start with this graph:

The initial values for the arrays look like this:

Now, we start with node a.

For every pair, we check to see if going through node a makes the path shorter. We notice this happens for the pairs (b,e) and (b,f) so we change both distances, and set the previous for each one to the id of node a (which is 0). The arrays now become:

Notice that as we discovered that the path bàaàf is shorter than bàf. We update the "previous" array entry of bàf with previous(a,f). In other words to go from b to f, the node immediately previous to f in this path is exactly equal to the node previous to f in the path from a to f. (This was a pretty tricky sentence. You probably need to read it twice!) [Editor's note: I did].

Next, we turn our attention to node 2. We do the same thing. This time, we find four improvements.

We can improve the paths (d,a), (d,c), (d,e), and (d,f). They now become

We keep doing the same thing, till we reach the final values for the arrays.

It's not a very straightforward algorithm like the previous one, I have to admit.

Next: Back to the water problem >>
 

More Development Cycles Articles
More By Mohamed Saad

Comments On: Learning About the Graph Construct using Games, Part II

>>> Be the FIRST to comment on this article!