Home arrow Development Cycles arrow Page 4 - Learning About the Graph Construct using Games, Part II

Learning About the Graph Construct using Games, Part II

In this second article in a three part series, we learn about two famous algorithms that can be used to solve the classic shortest path problem, and finally get the solution to the water jug division task set in the first part (no fair reading ahead to find it!).

Author Info:
By: Mohamed Saad
Rating: 5 stars5 stars5 stars5 stars5 stars / 33
March 15, 2005
  1. · Learning About the Graph Construct using Games, Part II
  2. · Dijkstra's algorithm
  3. · Algorithm in action
  4. · Floyd-Warshall algorithm
  5. · Back to the water problem

print this article

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 baf is shorter than bf. We update the "previous" array entry of bf 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.

blog comments powered by Disqus

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials