Learning About the Graph Construct using Games, Part II
(Page 1 of 5 )
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!).
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.
Next: Dijkstra's algorithm >>
More Development Cycles Articles
More By Mohamed Saad
