Dijkstra递归java.lang.StackOverflowError

我试图递归地编写Dijkstra算法。但我一直得到这个java.lang.StackOverflowError。Dijkstra递归java.lang.StackOverflowError

它使用PixelNode s，它具有灰度值和x,y坐标。邻居函数返回最大值3，即当前像素s下面的3个像素。

public PixelNode Dijkstra(PixelNode s, PriorityQueue<PixelNode> leads) { 
    s.visited = true; 
    if (s.isEndNode) { 
    return s; 
    } 
    ArrayList<PixelNode> nbs = s.neighbors(); 
    for (PixelNode nb : nbs) { 
    if (!nb.visited) { 
     float new_distance = s.distance + nb.val(); 
     if (new_distance < nb.distance) { 
     nb.distance = new_distance; 
     nb.via = s; 
     } 
     if (!nb.addedToLeads) { 
     nb.addedToLeads=true; 
     leads.add(nb); 
     } else { 
     leads.remove(nb); 
     leads.add(nb); 
     } 
    } 
    } 
    return Dijkstra(leads.poll(), leads); 
}

如果有人会如此友善地帮助我，那将是非常感谢！编号： leads.remove（nb）不起作用。没有正确覆盖PixelNode的equals函数。现在我已经正确覆盖它仍然没有删除，虽然...

编辑：我开始认为它已达到最大递归深度。如果我将图像裁剪得很小，它会找到正确的路径...对于21x19的图像，它需要374次递归。大概是图像中的像素数。真实图像是396x366。我想它需要396x366 = 144936递归函数调用。它打破3257电话。

功能的新版本，现在是：

public PixelNode dijkstra(PixelNode s, PriorityQueue<PixelNode> leads) { 
    s.visited=true; 
    if(s.isEndNode) { 
    return s; 
    } 
    ArrayList<PixelNode> nbs = s.neighbors(); 
    for(PixelNode nb : nbs) { 
    if(!nb.visited) { 
     float new_distance = s.distance + nb.val(); 
     if(new_distance < nb.distance) { 
     nb.distance = new_distance; 
     nb.via = s; 
     nb.addedToLeads = true; 
     leads.add(nb); 
     } 
    } 
    } 
    return dijkstra(leads.poll(), leads); 
}

来源

2013-10-05 Erik vd H

StackOverflowError异常的名称永远不会让我觉得/看起来很严重:) –

你确定任何一个节点设置为's.isEndNode = true' – JavaDeveloper

如果像素s的索引位于底部它应该停止搜索的图像行。 s.isEndNode =（s.i> =（img.pixels.length - img.width）&& s.i

虽然我没有源代码来重现问题，我必须猜测：

public PixelNode Dijkstra(PixelNode s, PriorityQueue<PixelNode> leads) { 
    s.visited = true; 
    if (s.isEndNode) { 
    return s; 
    } 
    ArrayList<PixelNode> nbs = s.neighbors(); 
    for (PixelNode nb : nbs) { 
    if (!nb.visited) { 
     float new_distance = s.distance + nb.val(); 
     if (new_distance < nb.distance) { 
     if (nb.addedToLeads) { 
      // already in leads with higher distance value 
      // Note: remove is done before distance update 
      leads.remove(nb); 
     } 
     nb.distance = new_distance; 
     nb.via = s; 
     } else if (nb.addedToLeads) { 
     // already in leads with lower or equal distance value 
     continue; 
     } 
     nb.addedToLeads=true; 
     leads.add(nb); 
    } 
    } 
    return Dijkstra(leads.poll(), leads); 
}

另外，还要确保你的比较为PriorityQueue返回等于的正确值。

来源

2013-10-05 19:03:18

感谢您的提示！我认为删除并不是真正需要的，因为新的插入将在队列中更高。我认为它永远不会以更高的距离轮询它的“克隆”。 –

Dijkstra递归java.lang.StackOverflowError

回答

相关问题