我試圖遞歸地編寫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);
}
StackOverflowError異常的名稱永遠不會讓我覺得/看起來很嚴重:) –
你確定任何一個節點設置爲's.isEndNode = true' – JavaDeveloper
如果像素s的索引位於底部它應該停止搜索的圖像行。 s.isEndNode =(s.i> =(img.pixels.length - img.width)&& s.i