Dijkstra算法在計算多個路徑時失敗

我正在嘗試爲多個節點實現Dijkstra算法。例如，我有x個要訪問的節點，我需要制定一條路徑來訪問每個節點而不改變它們的順序，如果路徑比這更短，則無關緊要。似乎一切似乎都起作用，但是在超過2個節點之後，它在計算路線時失敗並且內存不足。我假設我在這裏做了很糟糕的事情。Dijkstra算法在計算多個路徑時失敗

對於這個不清楚的問題，我很抱歉，但我不確定如何縮短它。

編輯：問題是，當在'verticesToVisit'列表中添加3個或更多個頂點時，Java在'getShortestPath方法的Java堆空間異常中拋出內存不足，精確的行在下面用註釋標記。

反正這裏是我的類：

Vertice 

private List<Edge> adjencies; 
private double minDistance = Double.POSITIVE_INFINITY; 
private Vertice previous; 

public Domicile() { 
    adjencies = new ArrayList<Edge>(); 
    previous = null; 
} 
public void reset() { 
    this.minDistance = Double.POSITIVE_INFINITY; 
} 
// sets and gets..

邊緣

private Vertice target; 
private Vertice source; // Not used in algorithm, just for debugging 
private double weight; 

public Edge(Vertice argSource, Vertice argTarget, double argWeight) { 
    source = argSource; 
    target = argTarget; 
    weight = argWeight; 
} 
public Edge(){} 
// sets and gets

算法：

public void computePaths(Vertice source) { 
    source.setMinDistance(0.); 
    PriorityQueue<Vertice> vertexQueue = new PriorityQueue<Vertice>(); 
    vertexQueue.add(source); 
    while(!vertexQueue.isEmpty()) { 
     Vertice u = vertexQueue.poll(); 

     for(Edge e : u.getAdjencies()) { 
      Vertice v = e.getTarget(); 
      double weight = e.getWeight(); 
      double distanceThroughU = u.getMinDistance() + weight; 
      if(distanceThroughU < v.getMinDistance()) { 
       vertexQueue.remove(v); 
       v.setMinDistance(distanceThroughU); 
       v.setPrevious(u); 
       vertexQueue.add(v); 
      } 
     } 
    } 
} 
/////////////////////// 
// This method fails // 
/////////////////////// 
public List<Vertice> getShortestPathTo(Vertice target) { 
    List<Vertice> path = new ArrayList<Vertice>(); 
    for(Vertice vertex = target; vertex != null; vertex = vertex.getPrevious()) { 
     path.add(vertex); // Java runs out of memory "Java heap size" here 
    } 
    Collections.reverse(path); 
    return path; 
} 

public void resetAllVertices() { 
    for(Vertice dom : graph) { 
     dom.reset(); 
    } 
} 


public List<String> getRoute() { 
    List<Vertice> verticesToVisit = dbd.getAllVertice(); // Gets them from database. This part is working. 
    Collections.sort(verticesToVisit); 
    List<String> result = new ArrayList<String>(); 
    if(verticesToVisit.isEmpty()) { 
     return null; 
    } 
    else if(patients.size() < 2) { 
     result.add(verticestoVisit.get(0).getName()); 
    } else { 

     for(int i = 0; i < verticesToVisit.size()-1; i++) { 
      Vertices graphDomStart = findFromGraph(verticesToVisit.get(i).getLocationId()); // finds vertice in graph (in db they dont have edges) 
      Vertice graphDomGoal = findFromGraph(verticesToVisit.get(i+1).getLocationId()); // finds vertice in graph (in db they dont have edges) 

      computePaths(graphDomStart); // exception is tracked from here 
      result.add(formatAddress(getShortestPathTo(graphDomGoal))); 

      resetAllVertices(); 
     } 
    } 
    return result; 
} 

private Domicile findFromGraph(int locationId) { 
    for(Domicile dom : graph) { 
     if(dom.getLocationId() == locationId) { 
      return dom; 
     } 
    } 
    return null; 
}

感謝您在百忙之中的代碼大牆。

來源

2015-05-26 Edgar.A

您需要將問題和代碼集中到相關部分。該算法是否適用於1個源-1目標？代碼的哪部分被懷疑是有問題的。還請提供一個示例，顯示錯誤行爲 - 以及預期行爲 – amit

在你復位功能：

public void reset() { 
    this.minDistance = Double.POSITIVE_INFINITY; 
}

我建議你也復位以前

public void reset() { 
    this.minDistance = Double.POSITIVE_INFINITY; 
    this.previous = null; 
}

或向後跟蹤路徑時，你會得到一個無限循環。

來源

2015-05-26 18:46:21

這就是整個問題，幾小時的挫折就結束了一行修復，這就是爲什麼我喜歡編程非常感謝.. –

Dijkstra算法在計算多個路徑時失敗

回答

相關問題