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

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
TABLE OF CONTENTS:
  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
SEARCH DEVARTICLES

Learning About the Graph Construct using Games, Part II - Back to the water problem
(Page 5 of 5 )

We have now described both algorithms, so let's return to the problem at hand. I hope you haven't forgotten our problem was actually to find the steps needed to divide eight liters of water into two fours. All that we have explained was just background to get us back into the problem we are solving!

In the previous part we described how to construct the graph. All that remained was to find the shortest path from the "8","0","0" node to the "4","4","0" node.

Since we are not interested in all the pairs for the shortest path, it would be much easier to use Dijkstra's algorithm to find the single source shortest path starting at the "8","0","0" node.

Here is the source code we need to add to the previous part:

First, we added the three arrays required by the algorithm:

int[] distance;

boolean[] found;

int[] prev;

Next, this is the function that chooses the node that was not visited, and having the smallest distance:

int choose()

{

  int min=10000000;

  int minPos=-1;

  for(int i=0;i<data.size();i++)

    {

      if(distance[i]<min&&!found[i])

        {

          min=distance[i];

            minPos=i;

        }

    }

  return minPos;

}

This is not a very hard function. All it does is find the node with the smallest distance that has not been visited before.

Next, here is the function that actually finds the shortest path. This is the actual implementation of Dijkstra's algorithm.

void findPath()

{

  distance=new int[data.size()];

  found=new boolean[data.size()];

  prev=new int[data.size()];

  //prepare 3 arrays

  for(int i=0;i<data.size();i++)

    distance[i]=1000000;

  //node 0 is the one we will start from

  //so, prepare distances of nodes directly connected to it

  node2 t=((node)(data.elementAt(0))).links;

  while(t!=null)

    {

      distance[t.id]=1;

      t=t.next;

    }

  distance[0]=0;

  found[0]=true;

  //do the real work

  for(int i=0;i<data.size()-2;i++)

    { //find nearest node

      int u=choose();

      found[u]=true;

      //see if we can improve distances to other nodes

      for(int w=0;w<data.size();w++)

        {

          if(!found[w])

            {

              if(distance[u]+getCost(u,w)<distance[w])

                {

                  distance[w]=distance[u]+getCost(u,w);

                  prev[w]=u;

                }

            }

        }

    }

}

This function is pretty straightforward too. It just performs the algorithm we mentioned step by step.

Finally, here is a function to display the actual steps needed. As noted earlier, Dijkstra's algorithm finds, for every node, the node previous to it. This function, therefore, prints the path in reverse order! It is extremely easy to modify it to print the path in the correct order (you can add a vector of Tuples, add the solution steps to it, then print it backward); this is left as an exercise.

void print

{

  int ourTarget=0;

  //find the index of the "4", "4","0" node

  for(int w=0;w<data.size();w++)

    {

      if(((node)(data.elementAt(w))).data.a==4&&((node)(data.elementAt(w))).data.b==4)

        ourTarget=w;

    }

    while(ourTarget!=0)

      {

        System.out.print("Step: "+(((node)(data.elementAt(ourTarget))).data.a)+" "+(((node)(data.elementAt(ourTarget))).data.b)+" "+(((node)(data.elementAt(ourTarget))).data.c)+"->");

        ourTarget=prev[ourTarget];

      }

    //print last step

    System.out.print("Step "+(((node)(data.elementAt(ourTarget))).data.a)+" "+(((node)(data.elementAt(ourTarget))).data.b)+" "+(((node)(data.elementAt(ourTarget))).data.c)+"->");

}

Whew, we have done something great. We have finally solved the problem at hand! And not just that: this category of problems is over! We can solve any variations with minimal changes. For example, a famous variation was to do the same problem but with jugs of capacities 12, 9 and 7 liters; we needed to divide 12 liters into two sixes. It is very easy to make this modification now, isn't it?

Oh, and if you don't have the time to actually run the program, here is the solution. It takes only 7 steps to solve this problem:

Initial capacities: 8,0,0

Jug 1 Jug 2: 3,5,0
Jug 2 Jug 3: 3,2,3
Jug 3 Jug 1: 6,2,0
Jug 2 Jug 3: 6,0,2
Jug 1 Jug 2: 1,5,2
Jug 2 Jug 3: 1,4,3
Jug 3 Jug 1: 4,4,0

And, that concludes part two of this three part series. What is to come in the next part? We are going to handle a totally new game, and see what we can do. We are going to be talking about Euler tours, simple paths and simple loops.

Remember, if you have any questions, suggestions, or comments, you can always drop me an email at msaad@themagicseal.com, I would like to hear from you.

Good Luck!


DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- 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 
Support 

Developer Shed Affiliates

 




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