BFS改性

Question

我试图找到所有最短的路径，其中所有的路径都有值1。我使用了修改的BFS。我也在队列中添加了封闭节点。当我找到终端节点时，我停止添加节点，只计算队列中的结束节点。但它不适用于我的测试输入。为什么我的主意不好？

伪码

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

下面是代码中的一些问题：

1. 无限循环：在没有从源到目标的路径的情况下--但是图中有一个循环，您的算法应该返回0 --但是，它被卡在无限循环中。
2. 计数错误路径：让我们假设target在source的深度4中，并由path source->v1->v2->target到达。现在，假设您在图中也有一个路径source->v3->v4->v5->target，并且由于某种原因，v4在target之前被插入到队列中(这是可能发生的，在这2中没有对顺序的限制)。您还将再次将target添加到边缘(v5,target)的队列中，并计算路径source->v3->v4->v5->target，但这不是最短路径--但您确实计算了它.

例如，查看一下这个图表：

​

在上面，您首先从s开始，并将它的所有邻居添加到队列中。现在，让我们假设v2是在v1之前添加的(这是可以发生的，没有什么可以阻止它)

现在，在下一步中，将展开v2，并将v3添加到队列中。

接下来，处理v1并将target添加到队列中。

现在，v3被处理，并再次将target添加到队列中。

现在，target被处理，count增加，标志found被设置。

队列尚未空，您现在处理target -并再次增加count。

因此，当完成- count == 2时，只有一条最短的路径.之所以会出现这种情况，是因为您还计算了路径s->v2->v3->t。