在找到两个节点之间的最短路径时避免循环

Question

我编写了一种方法来查找加权图中两个节点之间的所有可能路径。边可以是有向的或无向的。在大多数情况下，下面的算法正在运行并检索路径，就像我期望的那样。

但是，当节点 A 和 B 之间存在无向边时，它会从 B 循环回到 A 并将其包含在路径列表中。我将其输入为伪代码，因为这是一项作业，我不想让我的代码出现在互联网上：

Function(findPaths)
{
    currPaths -> LinkedList
    currPath -> add(StartingNode) 
    findPathsRecurs(StartNode, FinishNode, currPaths)
}

Function(findPathsRecurse)
{
    storePaths -> LinkedList
    for(All adjacent nodes V to StartNode)
    {
        if(V->visited)
        {
             if(V = FinishNode)
             {
                  currPath -> add(V)
                  storePaths -> add(currPath)
                  currPath -> remove(V)
             }
        }
    }
    for(All adjacent nodes V2 to StartNode)
    {
         if(V2->not visited OR V2->not = FinishNode)
         {
              currPaths->add(V2)
              v2->visit

              findAllPathsRecurs(v2, FinishNode, currPaths)
              currPaths->removeFromBack
              v2->unvisit
         }
    }
}

从某个节点 A 到节点 D 的预期输出：

Path 1: A->B->C->D
Path 2: A->B->D

某些节点 A 到节点 D 的实际输出：

Path 1: A->B->C->D
Path 2: A->B->D
Path 3: A->B->A->C->D

如果我在第一个 for 循环中将节点标记为已访问，然后在该循环结束之前未访问，则不会发生任何变化，这是可以预期的。如果我只是将它标记为已访问而不取消访问（在第一个 for 循环中），那么代码只存储一个路径，这也是有道理的。

我在解决这个问题时遇到了问题，如有任何帮助，我们将不胜感激！

Answer 1

过滤掉任何两次访问同一节点的路径。

在找到两个节点之间的最短路径时避免循环

Avoiding cycles when finding shortest path between two nodes

graph-theory