看似正确的BFS实现查找路径，但不是*最短路径(失重边)

下面是一个算法的尝试，该算法可以在具有失重边的图中找到最短路径，并添加了一个约束：一组不能在路径中的节点。因此，它不是找到节点之间的绝对最短路径，而是找到不包括某些节点的最短路径。

Wordnode是节点类，而HashSet avoids则是必须避免的节点集。算法中唯一发挥作用的地方是检查是否向队列中添加节点。如果它在avoid中(或者如果它已经被访问过(，不要添加它。我认为这个检查的效果应该相当于暂时删除evoid中节点的任何边，尽管通过使用哈希集，我可以避免实际更改数据结构。

我认为算法是有效的，直到我通过向添加单词来避免，从而使路径更短。例如，如果避免为空，则对于最短路径(A，Z，｛｝。。。

我使用的图有数千个节点，但我已经检查了(A、B、E、C、F、L、D、Z(和(A、R、K、Z(是否都是有效路径。问题是，当避免为空时，当明显存在长度仅为4的路径时，算法返回长度为8的路径。

这表明我的算法(如下(不正确，或者我的图形数据结构有问题。检查后者会更困难，所以我想我会先看看是否有人发现下面的问题。

那么，你能看到下面的算法在避免为非空时比为空时找到更短路径的原因吗？

注意："this"是原点，dest(dest(是一个参数。

感谢

public LinkedList<String> shortestPath(Wordnode dest, int limit, HashSet<Wordnode> avoids)
{
    HashSet<Wordnode> visited = new HashSet<>();
    HashMap<Wordnode, Wordnode> previous = new HashMap<>();
    LinkedList<Wordnode> q = new LinkedList<Wordnode>();
    previous.put(this, null);
    q.add(this);
    Wordnode curr = null;
    boolean found = false;
    while(!q.isEmpty() && !found)
    {
        curr = q.removeLast();
        visited.add(curr);
        if(curr == dest)
            found = true;
        else
        {
            for(Wordnode n: curr.neighbors)
            {
                if(!visited.contains(n) && !avoids.contains(n))
                {
                    q.addFirst(n);
                    previous.put(n, curr);
                }
            }
        }
    }
    if(!found)
        return null;
    LinkedList<String> ret = new LinkedList<>();
    while(curr != null)
    {
        ret.addFirst(curr.word);
        curr = previous.get(curr);
    }
    return ret;
}

我认为您的问题是如何使用previous映射构建边列表。在对节点进行排队时，可以存储最后一条看到的边，但这条边可能不在最短路径上。

从队列中提取dest时会检查它，但dest节点的previous中存储的边可能不再是添加到队列时到达dest的边。

当您提供avoids节点时，您将跳过更新previous中的边的过程，因此可能会以更短的路径结束-这不是是否指定了avoids，而是avoids是否包含可能"损坏"边列表的较长路径上的节点。

您的BFS是正确的。问题是如何编写找到的路径。BFS中的最短路径表示"从源到目的地的级别数"。但是，您正在计算从源到目的地的过程中查看的唯一节点的数量。

考虑3个节点相互连接的图：

路径A-C为1级长。您的实现可以给出路径长度2，因为节点可以以A-B和C的形式访问。顺序将取决于您的输入数据。所以你需要计算等级。

我在这里添加了一个答案，因为前面的答案都没有表示正确的错误。

问题是节点在哪里被标记为已访问：在最初的情况下，这是在节点从队列中弹出时完成的，这意味着在给定节点到达队列顶部之前，它可能会被添加几次，从而改变路径构造。

在排队时，您必须标记您的节点，因此，在行队列之后。addFirst(n(刚刚添加visited.add(n(.

相关内容

最新更新

热门标签：