0

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

它使用PixelNode具有灰度值和x,y坐标的 s。邻居函数返回 max 3 PixelNodes，即当前像素 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 次递归。大约是图像中的 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);
}
4

1 回答 1

0

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

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 的 Comparator 返回正确的 equals 值。

于 2013-10-05T19:03:18.297 回答