计算多条路径时 Dijkstra 算法失败

Question

我正在尝试为多个节点实施 Dijkstra 算法。例如，我有 x 个要访问的节点，我需要在不更改顺序的情况下创建一条路径来访问每个节点，如果有比这更短的路径也没关系。一开始似乎一切正常，但在超过 2 个节点后，它无法计算路由并耗尽内存。我假设我在这里做了一些糟糕的事情。

对于这个不清楚的问题，我深表歉意，但我不确定如何缩短它。

编辑：问题是当 'verticesToVisit' 列表中添加了 3 个或更多顶点时，Java 在 Java 堆中抛出内存不足 space 异常在 'getShortestPath 方法中，确切的行在下面用注释标记。

无论如何这是我的类:

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;
}

谢谢你，抱歉代码太长了。

Answer 1

在你的重置函数中：

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

我建议你也重置以前的

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

否则在向后追踪路径时会出现无限循环。

计算多条路径时 Dijkstra 算法失败

Dijkstra algorithm fails when calculating multiple paths

java

algorithm

dijkstra