Home arrow Development Cycles arrow 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
(Page 1 of 5 )

Welcome back! This is part two of the three part series entitled "Playing games with graphs." In part one, we gave an introduction to graphs, and introduced the problem of water division. We saw how we can construct the graph for this problem. Today, we are going to handle finding the shortest path from the source node to the destination node.

Recall from part one that in the graph constructed, a node represented a state of the jugs. The initial state was "8","0","0" or 8 liters in the first jug, with other two jugs empty. We constructed a graph of all possible states that can be reached. We needed to find the shortest path from the node "8","0","0" to the node "4","4","0"

Shortest path problem

The shortest path problem is quite straightforward. Given two nodes in a graph, it is necessary to find the shortest path between them. Luckily for us, the shortest path problem is an easy problem to solve, unlike the longest path problem, which surprisingly, is a very hard problem to solve. This is one of the rare occasions in life where the more useful problem is also the easier one. But let's set theory aside for now, we have a task to do.

There are two very famous algorithms for finding the shortest path in a graph. Those are the ones we are going to introduce here.

The first algorithm starts with a node, and proceeds to find the shortest path from this node to all other nodes in the graph. This is called the single-source all-destination shortest path for obvious reasons. This algorithm was devised by Dijkstra.

The other algorithm just finds the shortest path from every node in the graph to every other node. This is obviously called all-source all-destination. This algorithm was developed by Floyd and Warshall.

As you may imagine, the Floyd-Warshall algorithm is a little harder to comprehend than Dijkstra's algorithm (simply because it does more). We are going to present both ideas first, and then we are going to show all the details behind Dijkstra's algorithm to solve the problem at hand.


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