2013-10-05 97 views
0

我試圖遞歸地編寫Dijkstra算法。但我一直得到這個java.lang.StackOverflowErrorDijkstra遞歸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); 
} 
+0

StackOverflowError異常的名稱永遠不會讓我覺得/看起來很嚴重:) –

+0

你確定任何一個節點設置爲's.isEndNode = true' – JavaDeveloper

+0

如果像素s的索引位於底部它應該停止搜索的圖像行。 s.isEndNode =(s.i> =(img.pixels.length - img.width)&& s.i

回答

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返回等於的正確值。

+0

感謝您的提示!我認爲刪除並不是真正需要的,因爲新的插入將在隊列中更高。我認爲它永遠不會以更高的距離輪詢它的「克隆」。 –