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.
Best Answer
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).