递归Dijkstra递归java。StackOverflowerr先生

Question

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

它使用具有灰度值和x,y坐标的PixelNode。邻居函数返回最大3PixelNodes，即当前像素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);
}

如果有人能帮助我，我将不胜感激

编辑： 引导。移除（nb）不起作用。没有正确覆盖PixelNode的equals函数。现在我已经正确地覆盖了它，但它仍然没有被删除

编辑： 我开始认为它已经达到了最大递归深度。如果我把图像裁剪得很小，它会找到正确的路径。。。对于21x19的映像，它需要374个递归。大致是图像中像素的nr。真实图像是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);
}

Answer 1

虽然我没有源代码来重现这个问题，但我不得不猜测：

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的比较器返回正确的等于值