Databases
StackOverflow2013
Postsdbo
POJava out of Memory heap error when calculating shortest paths to all nodes through Dijkstra's algorithm from every node as source
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POJava out of Memory heap error when calculating shortest paths to all nodes through Dijkstra's algorithm from every node as source
    text
    copied!<p>I have a network of 7 nodes and 8 links. I have taken the following classes from examples on the internet. I want to calculate the shortest paths from every node to all other nodes. For that, I have written the required <strong>for</strong> loop in Solve (main). But, I am getting the shown output. Shortest paths are fine from the first node, Harrisburg. From the second node, the java out of memory occurs. What do I have to do? Thanks for any help. </p> <p>Vertex.java</p> <pre><code> public class Vertex implements Comparable&lt;Vertex&gt; { 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); } } </code></pre> <p>Edge.java</p> <pre><code>public class Edge { public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { this.target = argTarget; this.weight = argWeight; } } </code></pre> <p>Dijkstra.java</p> <pre><code>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&lt;Vertex&gt; vertexQueue = new PriorityQueue&lt;Vertex&gt;(); 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 &lt; 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&lt;Vertex&gt; getShortestPathTo(Vertex target) { List&lt;Vertex&gt; path = new ArrayList&lt;Vertex&gt;(); for (Vertex vertex = target; vertex != null; vertex = vertex.previous) { path.add(vertex); } Collections.reverse(path); return path; } } </code></pre> <p>Solve.java</p> <pre><code>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 &lt; 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&lt;Vertex&gt; 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); } } ........ </code></pre> <p>Output:</p> <pre><code>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) </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload