Dijkstra의 알고리즘을 통해 소스로 모든 노드에서 모든 노드에 대한 최단 경로를 계산할 때 Java 메모리 부족 힙 오류가 발생했습니다.

Question

네트워크가 7 노드와 8 링크입니다. 인터넷에서 다음과 같은 수업을 들었습니다. 모든 노드에서 다른 노드까지의 최단 경로를 계산하고 싶습니다. 이를 위해 Solve (main)에서 루프에 대해 을 작성했습니다. 그러나, 나는 출력을 얻고있다. 최단 경로는 첫 번째 노드 Harrisburg에서 잘됩니다. 두 번째 노드에서 Java Out of Memory가 발생합니다. 나는 무엇을해야합니까? 어떤 도움을 주셔서 감사합니다.

Vertex.java

public class Vertex implements Comparable<Vertex> { 

    public final String name; 
    public Edge[] adjacencies; 
    public double minDistance = Double.POSITIVE_INFINITY; 
    public Vertex previous; 
    public double population, employment; 
    public double targetPopulation, targetEmployment; 

    public Vertex (String argName, double population, double employment, double targetPopulation, double targetEmployment) { 
     this.name = argName; 
     this.population = population; 
     this.employment = employment; 
     this.targetPopulation = targetPopulation; 
     this.targetEmployment = targetEmployment; 
    } 

    public String toString() { 
     return name; 
    } 

    //Vertex comparator 
    @Override 
    public int compareTo(Vertex other) { 
     // TODO Auto-generated method stub 
     return Double.compare(minDistance, other.minDistance); 
    } 

    } 

Edge.java

public class Edge { 

public final Vertex target; 
public final double weight; 

public Edge(Vertex argTarget, double argWeight) { 
    this.target = argTarget; 
    this.weight = argWeight; 
} 

} 

Dijkstra.java

public class Dijkstra { 

//simple compute paths function 
public void computePaths(Vertex source) { 
    source.minDistance = 0.; 

    //Visit each vertex u, always visiting vertex with smallest minDistance first 
    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); 
    vertexQueue.add(source); 

    while (!vertexQueue.isEmpty()) { 
     Vertex u = vertexQueue.poll(); 

     //Visit each edge exiting u 
     for (Edge e : u.adjacencies) { 
      Vertex v = e.target; 
      double weight = e.weight; 

      //relax the edge (u,v) 
      double distanceThroughU = u.minDistance + weight; 
      if(distanceThroughU < v.minDistance) { 
       //remove v from queue 
       vertexQueue.remove(v); 

       v.minDistance = distanceThroughU; 
       v.previous = u; 

       //re-add v to queue 
       vertexQueue.add(v); 
      } 
     } 
    } 


} 

//get shortest path function 
public List<Vertex> getShortestPathTo(Vertex target) { 
    List<Vertex> path = new ArrayList<Vertex>(); 
    for (Vertex vertex = target; vertex != null; vertex = vertex.previous) { 
     path.add(vertex); 
    } 

    Collections.reverse(path); 
    return path; 
} 

} 

Solve.java

Vertex v0 = new Vertex("Harrisburg", 5, 0.5, 9, 5); 
Vertex v1 = new Vertex("Baltimore", 61, 21, 91, 32); 
Vertex v2 = new Vertex("Washington", 99, 10, 10, 10); 
Vertex v3 = new Vertex("Philadelphia", 159, 30, 100, 45); 
Vertex v4 = new Vertex("Binghamton", 10, 10, 10, 10); 
Vertex v5 = new Vertex("Allentown", 10, 10, 10, 10); 
Vertex v6 = new Vertex("New York", 891, 200, 400, 220); 

v0.adjacencies = new Edge[] { new Edge(v1, distances[0]), 
           new Edge(v5, distances[1]) }; 

    v1.adjacencies = new Edge[] { new Edge(v0, distances[0]), 
           new Edge(v2, distances[2]), 
           new Edge(v3, distances[3])}; 

    v2.adjacencies = new Edge[] { new Edge(v1, distances[2])}; 

    v3.adjacencies = new Edge[] { new Edge(v1, distances[3]), 
           new Edge(v5, distances[4]), 
           new Edge(v6, distances[5])}; 

    v4.adjacencies = new Edge[] { new Edge(v5, distances[6])}; 

    v5.adjacencies = new Edge[] { new Edge(v0, distances[1]), 
           new Edge(v3, distances[4]), 
           new Edge(v4, distances[6]), 
           new Edge(v6, distances[7]) }; 

    v6.adjacencies = new Edge[] { new Edge(v3, distances[5]), 
           new Edge(v5, distances[7]) }; 

Vertex[] vertices = {v0, v1, v2, v3, v4, v5, v6}; 

Dijkstra dijkstra = new Dijkstra(); 

........ 

for(int i = 0; i < vertices.length; i++) { 

        for(Vertex v : vertices) { 
      v.setMinDistance(Double.POSITIVE_INFINITY); 
     } 
     dijkstra.computePaths(vertices[i]); 
     //print out shortest paths and distance 

     System.out.println("Shortest paths from "+ vertices[i].name); 
     for (Vertex v: vertices) { 
      System.out.println("Distance to " + v + ": " + v.minDistance); 
      List<Vertex> shortestPath = dijkstra.getShortestPathTo(v); 
      System.out.println("Path: " + shortestPath); 

      currentAccE[i] = currentAccE[i] + (v.employment)*impedance(v.minDistance); 
      currentAccP[i] = currentAccP[i] + (v.population)*impedance(v.minDistance); 

     } 
    } 

........ 

출력 :

Solve started.......... 
Shortest paths from Harrisburg 
Distance to Harrisburg: 0.0 
Path: [Harrisburg] 
Distance to Baltimore: 79.0 
Path: [Harrisburg, Baltimore] 
Distance to Washington: 118.0 
Path: [Harrisburg, Baltimore, Washington] 
Distance to Philadelphia: 142.0 
Path: [Harrisburg, Allentown, Philadelphia] 
Distance to Binghamton: 214.0 
Path: [Harrisburg, Allentown, Binghamton] 
Distance to Allentown: 81.0 
Path: [Harrisburg, Allentown] 
Distance to New York: 172.0 
Path: [Harrisburg, Allentown, New York] 
Shortest paths from Baltimore 
Distance to Harrisburg: 79.0 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
at java.util.Arrays.copyOf(Arrays.java:2760) 
at java.util.Arrays.copyOf(Arrays.java:2734) 
at java.util.ArrayList.ensureCapacity(ArrayList.java:167) 
at java.util.ArrayList.add(ArrayList.java:351) 
at umd.sapeksha.shortestpath.Dijkstra.getShortestPathTo(Dijkstra.java:48) 
at umd.sapeksha.shortestpath.Solve.main(Solve.java:109) 

Answer 1

당신은 다른 알고리즘이 어디를에 따라 분명히 다를 것이다 이전에 계산 된 최소 거리를 사용, Double.POSITIVE_INFINITY 당신이 소스를 변경할 때마다 당신의 정점의 minDistance를 다시 초기화해야 에서 시작하다.