Wolf cabbage and goat using dijkstra.

Question

A farmer has to cross a river with a wolf, a goat and a cabbage. He has a boat, but in the boat he can take just one thing. He cannot let the goat alone with the wolf or the goat with the cabbage. It’s obvious why.

What is the solution?

Ok So I know the two solutions and I arrived them with trial and error. Reaching dead ends and making smart moves. But I am interested to know the solution of this problem using Dijkstra's Algorithm. I do not know what my graph should represent and how to use the shortest path algorithm to solve this puzzle.

Answer 1

Let $W, G, C$ denote wolf, goat, cabbage. Let $F$ be the farmer. Here are all the possible states: \begin{align*} \newcommand{\sep}{\; \mid \;} &1 & WGCF &\sep &\text{(start)} \\ &2 & &\sep WGCF &\text{(goal)} \\ &3 & WCF &\sep G \\ &4 & G &\sep WCF \\ &5 & WGF &\sep C \\ &6 & C &\sep WGF \\ &7 & GCF &\sep W \\ &8 & W &\sep GCF \\ &9 & GF &\sep WC \\ &10 & WC &\sep GF \\ \end{align*} (In all other states either the wolf will eat the goat, or the goat will eat the cabbage.) This is a graph on $10$ vertices. There are edges as follows: \begin{align*} 1 &\to 10 \\ 2 &\to 9 \\ 3 &\to 6, 8, 10 \\ 4 &\to 5, 7, 9 \\ 5 &\to 4, 8 \\ 6 &\to 3, 7 \\ 7 &\to 4, 6 \\ 8 &\to 3, 5 \\ 9 &\to 2, 4 \\ 10 &\to 1, 3 \\ \end{align*}

Here is the graph:

You can then apply Djikstra's algorithm as usual (which is kind of silly, since the solution is obvious once you see the graph).

Answer 2

Design the states as $S | S'$ where $S$ denotes the objects on one side of the river and $S'$ denotes the objects on the other side of the river.

Example : $WC|G$ denotes wolf and cabbage is on one side and goat on the other.

Put the appropriate transitions and run Dijkstra's algorithm.

Answer 3

Dijkstra himself simplified the example problem by noting the symmetry between wolf and cabbage, see http://www.cs.utexas.edu/users/EWD/videos/EWD4.mpg.