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

回答

相關問題