Home arrow Development Cycles arrow Page 3 - 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 - Algorithm in action
(Page 3 of 5 )

This is the whole idea behind the algorithm. If it is still unclear, here is a quick example of this algorithm in action.

In this graph

We want to find shortest paths starting at node A.

Here are the arrays again in case you have forgotten them

At first, we choose the smallest distance to an unvisited node (see the arrays we created above), so we choose the node e. Its entry at distance is 5, and it is not visited yet.

Now, we check to see if going from a to e, and then to any other node makes any improvements, and indeed, we find that the path to f is improved. Now, we can move to f with a cost of 9, (move from a to e, which costs 5, and then move from e to f, which costs 4) so we update it.

Also, the path to c has been improved. The cost was infinity, now c can be reached with a cost of only 15. We update this one too. The arrays now become:

Next, we choose the smallest non-visited distance, so we pick f this time (its distance is only 9). We find that the path to d has been improved from infinity to only 29.

The arrays become:

The third time, we pick c, the distance to d is now improved from 29 to only 20.

The arrays become:

We keep doing the same, till the shortest path is found to every node.

We end up with

We can now easily know the shortest path from node a to any node.

For example, to get the path from node a to node d, we keep following the previous array till we reach node 0 (0 is the index of node a).

We get d 2 (this is c) 4 (this is e) 0 (this is a)

So, the path is aecd, whose length is 20.

That was the first algorithm; it wasn't very hard, was it?

Now, let's move on to the other algorithm.


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