通过 Dijkstra 算法从每个节点作为源计算到所有节点的最短路径时，Java 内存不足堆错误

Question

我有一个包含 7 个节点和 8 个链接的网络。我从互联网上的示例中学习了以下类(class)。我想计算从每个节点到所有其他节点的最短路径。为此，我在 Solve (main) 中编写了所需的 for 循环。但是，我得到了显示的输出。从第一个节点 Harrisburg 开始的最短路径很好。从第二个节点开始，java内存不足。我需要做什么？谢谢你的帮助。

顶点.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);
    }

    }

边缘.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;
}

}

解决.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

每次更改源时，您都需要将顶点的 minDistance 重新初始化为 Double.POSITIVE_INFINITY，否则算法将使用之前计算的最小距离显然会有所不同，具体取决于您从哪里开始。