java - Java 中的 Dijkstra 算法和源码变更

Question

因此，我正在尝试实现 Dijkstra 算法，以找到两个城市之间的最短路径。 到目前为止我的类(class)是:

Edge.java

package com.company;

public class Edge {

        private int weight;
        private Vertex startVertex;
        private Vertex targetVertex;

        public Edge(int weight, Vertex startVertex, Vertex targetVertex) {
            this.weight = weight;
            this.startVertex = startVertex;
            this.targetVertex = targetVertex;
        }

        public double getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public Vertex getStartVertex() {
            return startVertex;
        }

        public void setStartVertex(Vertex startVertex) {
            this.startVertex = startVertex;
        }

        public Vertex getTargetVertex() {
            return targetVertex;
        }

        public void setTargetVertex(Vertex targetVertex) {
            this.targetVertex = targetVertex;
        }
    }

然后是 Vertex.java

package com.company;

import java.util.ArrayList;
import java.util.List;

public class Vertex implements Comparable<Vertex> {

    private String name;
    private List<Edge> adjacenciesList;
    private boolean visited;
    private Vertex predecessor;
    private double distance = Double.MAX_VALUE;

    public Vertex(String name) {
        this.name = name;
        this.adjacenciesList = new ArrayList<>();
    }

    public void addNeighbour(Edge edge) {
        this.adjacenciesList.add(edge);
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public List<Edge> getAdjacenciesList() {
        return adjacenciesList;
    }

    public void setAdjacenciesList(List<Edge> adjacenciesList) {
        this.adjacenciesList = adjacenciesList;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public Vertex getPredecessor() {
        return predecessor;
    }

    public void setPredecessor(Vertex predecessor) {
        this.predecessor = predecessor;
    }

    public double getDistance() {
        return distance;
    }

    public void setDistance(double distance) {
        this.distance = distance;
    }

    @Override
    public String toString() {
        return this.name;
    }

    @Override
    public int compareTo(Vertex otherVertex) {
        return Double.compare(this.distance, otherVertex.getDistance());
    }
}

和 DijkstraShortestPath.java

    package com.company;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class DjikstraShortestPath {
        public void computeShortestPaths(Vertex sourceVertex){

            sourceVertex.setDistance(0);
            PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
            priorityQueue.add(sourceVertex);
            sourceVertex.setVisited(true);

            while( !priorityQueue.isEmpty() ){
                // Getting the minimum distance vertex from priority queue
                Vertex actualVertex = priorityQueue.poll();

                for(Edge edge : actualVertex.getAdjacenciesList()){

                    Vertex v = edge.getTargetVertex();
                    if(!v.isVisited())
                    {
                        double newDistance = actualVertex.getDistance() + edge.getWeight();

                        if( newDistance < v.getDistance() ){
                            priorityQueue.remove(v);
                            v.setDistance(newDistance);
                            v.setPredecessor(actualVertex);
                            priorityQueue.add(v);
                        }
                    }
                }
                actualVertex.setVisited(true);
            }
        }

        public List<Vertex> getShortestPathTo(Vertex targetVertex){
            List<Vertex> path = new ArrayList<>();

            for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
                path.add(vertex);
            }

            Collections.reverse(path);
            return path;
        }

    }

现在，在 Main 我正在尝试这样的事情:

public static void main(String[] args) throws IOException {
{
int i, j;
 DjikstraShortestPath shortestPath = new DjikstraShortestPath();
        shortestPath.computeShortestPaths(vertex[0]); // setting the source to vertex[0]
        for(i=0; i<cities.size(); i++)
        {
            System.out.println("from"+vertex[0]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
            System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
        }
shortestPath.computeShortestPaths(vertex[1]); //changing the source
for(i=0; i<cities.size(); i++)
        {
            System.out.println("from"+vertex[1]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
            System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
        }
}

我面临的问题是初始源(初始城市)顶点[0]在设置时会产生正确的结果:

例如:

from A to A the distance is 0.0 //A is the main source in this case vertex[0]
path: A

from A to F the distance is 13.5
path: A D C B F

现在当我将源切换到顶点[1]

from B to A the distance is 0.0 //wrong because it uses the data from the previous (vertex[0])
path: A //this is wrong too

from B to F the distance is 13.5
path: A D C B F //uses the previous info from vertex[0] even though the source is changed to vertex[1]

尝试将 DijkstraShortestPath.java 中的 getShortestPathTo 函数更改为此

public void getShortestPathTo(Vertex targetVertex){
            List<Vertex> path = new ArrayList<>();

            for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
                path.add(vertex);
            }
            Collections.reverse(path);
            for(int i = 0; i<path.size(); i++)
            {
                System.out.println(path.get(i).getName());
            }
            path.clear();

        }


    }

使所有顶点都未被访问，现在我面临“内存不足”问题。存在堆内存问题，我已经尝试了所有方法。

如有任何帮助，我们将不胜感激。

注意安全，大家待在家里!

Answer 1

在第一次调用 computeShortestPaths 期间，您写入所有已访问的顶点以及它们到源的距离。

在调用 computeShortestPaths 之前，您不会重置此信息，因此顶点会保留其距离和访问过的状态(if(!v.isVisited()) 确保您不要更新第一次调用中已访问过的节点的任何内容)。

因此，您需要清除两次调用之间 Vertex 对象中的所有信息，或者(更好)重构您的代码，以便此信息存储在 DjikstraShortestPath 对象中而不是顶点中，并且每次调用computeShortestPaths时都会重置。