Length of the solution calculation in Breadth-first

Question

I'm trying to figure out how to calculate the route cost on this graph (it's the missionaries and cannibals game)

I have my definition as:

Mi = Missionary on the initial side, C = Cannibal on the initial side, B = Boat [I = Boat in the Initial Side, F = Boat on the Final Side],
Mf = Missionary on the other side of the river, Cf = Cannibal on the other side of the river
State: (Mi, Ci, B, Mf ,Cf)
Initial Status: (3, 3, I, 0,0)
Final Status: (0, 0, F, 3,3)
Status Space (All the valid statuses): 
{(3,3,I,0,0),(3,2,F,0,1),(2,2,F,1,1),(3,1,F,0,2),(3,2,I,0,1),(3,0,F,0,3),(3,1,I,0,2),(1,1,F,2,2),(2,2,I,1,1),(0,2,F,3,1),(0,3,I,3,0),(0,1,F,3,2),(0,2,I,3,1),(2,2,I,1,1),(3,2,I,0,1),(0,0,F,3,3)}

Rules:

1.  Bote can only carry two people
2.  One person has to drive the boat
3.  Cannibals can't outnumber the missionaries or they the missionaries will be eaten. 
Cost: 1 per crossing. 

Exhaustive Search (or Brute Search):

(3, 3, I, 0, 0) -> (2, 2, F, 1, 1) -> (3,2,I,0,1), -> (3,2,I,0,1) -> (3,2,1,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,F,1,1) -> (0,2,F,3,1) -> (0,3,I,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (0,0,F,3,3)

According to me and the graph the route cost for Exhaustive Search would be 11.

How can I calculate the route cost for that graph for Breadth-first?

I do know that Breadth-first I have to separate the graphs on levels and it will test each node on that level against the final result (depending on the direction, clockwise, or counterclockwise) but I'm not sure if I should take each node as a crossing (I'm getting 14 as length of the solution). For instance in the image I take the crossing from (3,3,I,0,0) to (3,2,F,0,1) as 1 and then there isn't more child-nodes on that branch so I should get back to (3,3,I,0,0) in order to reach the branch of (2,2,F,1,1) this I don't know If I should count it too or not

To get 14 I'm doing. (3, 3, I, 0, 0) -> (3,2,F,0,1) -> (2,2,F,1,1) -> (3,1,F,0,2) -> (3,2,I,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,I,1,1) -> (0,2,F,3,1) -> (0,3,1,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (2,2,I,1,1) -> (0,0,F,3,3)

Because of this doubts I have troubles calculating the Length of the solution

Answer 1

I do not know how your sources define "route cost" (I've never heard that term).

There are two points of view I can imagine.

1. Length of the solution

   Once you reach a fitting leaf you have found your solution and can abort. The length of the solution, i.e. the number of steps you have to perform to get everybody across, is the length of the path from the root to that leaf.

2. Cost of the algorithm

   The number of steps the algorithm has to perform is different, of course; it may visit many nodes that are not part of the final solution. The details depend on the specific implementation at hand.

   Specifically, you seem to be concerned about backtracking out of dead ends. The usual way to implement BFS is using a queue which makes backtracking free since you don't actually do it; the next node to visit is already at the front of the queue.

   If you don't use a queue and backtrack explicitly, well, you get quadratic worst-case performance. Don't do it.

Answer 2

If you want to calculate the distance between two nodes using BFS, you could use the algorithm as described in the Wikipedia.

Maybe it's easier to understand how this works if you think of BFS as working in waves:

wave <- starting node
set all distances to infinity
d = 0
while wave is not empty:
     set the distance of all nodes in wave to d
     next_wave = all neighbors of nodes in wave with infinite distance
     d = d + 1
     wave = next_wave

The wave-front travels over the graph very much like the wave in a pond after you throw a stone in it. In this formulation you don't explicitly traverse edges forwards or backwards, so it's harder to get confused when to increase distances.