java看似正确的BFS实现查找路径,但不是最短路径(失重边)
下面是一个算法的尝试,该算法可以在一个无重边图中找到最短路径,并添加了一个约束:一组不能在路径中的节点。因此,它不是寻找节点之间的绝对最短路径,而是寻找不包括特定节点的最短路径
Wordnode是节点类,HashSet-avoids是必须避免的节点集。算法中唯一起作用的地方是检查是否将节点添加到队列中。如果它在中(或者已经被访问过),不要添加它。我相信这个检查的效果应该相当于在避免中临时删除节点中的任何边,尽管通过使用HashSet,我避免了数据结构的实际变化
我以为算法是有效的,直到我通过在中添加单词来设法缩短路径。e、 例如,如果避免是空的,那么对于最短路径(A,Z,{})它可能会返回(A,B,e,C,F,L,D,Z),但是在将e和C添加到避免并调用最短路径(A,Z,{e,C})时,我得到(A,R,K,Z),它更短
我使用的图有数千个节点,但我已经检查了(A、B、E、C、F、L、D、Z)和(A、R、K、Z)都是有效路径。问题是,当避免为空时,算法返回长度为8的路径,而显然存在长度仅为4的路径
这向我表明,要么我的算法(如下)不正确,要么我的图形数据结构存在问题。检查后者会更困难,所以我想我会先看看是否有人发现下面的问题
那么,你能看到下面的算法在避免为非空时比为空时找到更短路径的任何原因吗
注意:“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;
}
共 (0) 个答案