BFS modification

Question

Im trying to find all shortest path, where all paths have value 1. I used modified BFS. I was adding closed nodes into queue too. When I find the end node I stop adding nodes and just count the end node in the queue. But it doesn't work for my testing input. Why is my idea bad?

pseudocode

addIntoQueue(startNode)
while(!queueIsEmpty()){
   nodeMain = dequeue()
   if(nodeMain==stopNode){
      found=true
      count++
   }
   if(!found)
   for(all node in NodeNeighbors){
      if(node!=CLOSED){
         addToQueue(node)
      }
   }
   nodeMain=CLOSED
}

Answer 1

Here are some issues in your code:

1. Infinite loop: In case of no path from source to target - but there is a cycle in the graph, your algorithm should return 0 - however, it is stuck in an infinite loop instead.
2. Counting wrong paths: Let's assume the target is at depth 4 from the source, and is reached by the path source->v1->v2->target. Now, assume you also have a path source->v3->v4->v5->target in your graph, and for some reason v4 was inserted to the queue before target (it can happen, there is no restriction on the orderings among these 2). You would also add target again to the queue for the edge (v5,target), and also count the path source->v3->v4->v5->target, but this is not a shortest path - but you did count it...

Have a look on this graph for example:

In the above, you first start from s, and add all its neighbors to the queue. Now, let's assume v2 is added before v1 (that can happen, nothing prevents it..)
Now, at the next step, v2 will be expanded and you will add v3 to the queue.
Next, v1 is processed and target is added to the queue.
Now, v3 is processed and add target to the queue again.
Now, target is processed, count is increased, and the flag found is set.
The queue is not empty yet, you now process target - and increase count again.

As a result, when done - count == 2, but there is only 1 shortest path. This happens because you also counted the path s->v2->v3->t.