Water Jug problem in Die Hard 3 into a graph

Question

I need to create a weighted directed graph based on the water jug problem from the movie Die Hard 3 (http://www.wikihow.com/Solve-the-Water-Jug-Riddle-from-Die-Hard-3).

I need to create nodes for all the possible moves (fill, empty, pour). After I need to find the shortest path to the solution. But I am have trouble creating this graph. I am using my own created linked list/node.

ex) given 3 gallon, 5 gallon. Get 4 gallons in the 5 gallon jug. I need to create a graph of all the possible moves to get to 4 gallons. Each different gallon represents a different node.

Answer 1

Presumably each node holds two positive integers -- number of gallons in the 3-gal jug, number of gallons in the 5-gal jug. Arcs, aka edges (directed), are the "moves" (and labeled with the action the arc represents) -- apparently you also have an unnamed tap handy, since you can always fill either of the jugs; you can also always empty a jug away (so you also have a sink); and so forth (other moves all involve moving water from one gallon to the other, until either the first one is empty, or the second one is full). It's no doubt better to avoid generating legal but useless arcs ("moves"), such as "filling" a jug that's already full, or undoing a move you just made (such as emptying a jug you just filled from the tap), though adding such arcs will only mean a little more work, not an incorrect solution.

So start with (0, 0) -- both jugs full, as you have at the start. Clearly the two arcs from here take you to (3, 0) and (0, 5) respectively (filling one or the other from the tap), and so on.