java - 如何用Java打印Dijkstra算法的完整路径

Question

目前，仅打印最终顶点，最小距离似乎为无穷大。我似乎找不到问题所在，因为顶点没有添加到“最短路径”ArrayList 中。我还想打印出该路径所采用的所有边缘。非常欢迎任何建议以下是我的完整代码，谢谢!

编辑:我已按照短跑运动员的建议编辑了我的类(class)。

我的 Graph 类的 getNeighbours() 方法中存在错误。有关源的信息被添加为邻居，即使我试图获取它的邻居。

我也不确定如何打印边缘信息以及顶点信息。

非常感谢任何建议!

最短路径查找器

class ShortestPathFinder {
        private  Graph graph = new Graph();
        private  Vertex source = new Vertex(0, null);
        private Vertex destination = new Vertex(0,null);
        private  Map<Vertex,Double> minimumWeightToVertices = new HashMap();
        private  Map<Vertex,Vertex> previousVertex = new HashMap();
        private  Set<Vertex> visited =  new HashSet();

        private  Map<Vertex,Double> neighbors = new HashMap();

    public Optional<Path> findShortestPath(Graph graph, Vertex source, Vertex destination) {
        this.graph = graph;
        this.source = graph.getVertex(source);
        this.destination = graph.getVertex(destination);
        Optional<Path> pathFound = Optional.empty();

        //start queue at source vertex
        source.setDistance(0);
        PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(source);
        source.setVisited(true);

        while( !priorityQueue.isEmpty() ){
          // Getting the minimum distance vertex from priority queue
          Vertex actualVertex = priorityQueue.poll();   
          //get Neighbors of source vertex 
          neighbors = graph.getNeighbours(source);
        //find Neighbor with lowest weight
          for(Entry<Vertex, Double> neighbor : neighbors.entrySet()){             
                 Vertex v = neighbor.getKey();
                if(v == destination) {
                    minimumWeightToVertices.put(v,v.getDistance());
                    v.setPredecessor(actualVertex);
                    previousVertex.put(actualVertex,v);
                    priorityQueue.add(v);
                    // found, set pathFound = Optional.of(path) 
                    Path path = new Path();
                    pathFound = Optional.of(path);
                }
                else if(visited.contains(v) == false)
                {
                    double newDistance = actualVertex.getDistance() + neighbor.getValue();

                    //when found min add to minmumWeightToVertices
                    if( newDistance < v.getDistance() ){
                        priorityQueue.remove(v);
                        v.setDistance(newDistance);
                        minimumWeightToVertices.put(v,newDistance);
                        v.setPredecessor(actualVertex);
                        previousVertex.put(actualVertex,v);
                        priorityQueue.add(v);
                        System.out.println("Added: " + v.getID());
                    }
                }
            }
           //When visited add to visited so not visited again
            actualVertex.setVisited(true);
            visited.add(actualVertex);  
          //continue getting neighbors with lowest index until destination reached 
        }       
        return pathFound;       
    }

    public void getPath() {     
        //print all info using previous Vertex and print out edge info from it
        for (Entry<Vertex, Vertex> entry : previousVertex.entrySet()) {
            System.out.println("ID: " + entry.getKey().getID() + " Name: " + entry.getKey().getName() +
                    " to  "  + "ID: " + entry.getValue().getID() + " Name: " + entry.getValue().getName());
        }
    }
}

图表

class Graph {
    private final Set<Vertex> vertices = new HashSet<Vertex>();
    private final Set<Edge> edges = new HashSet<Edge>();


    public void addVertex(int id, String name) {
        Vertex vertex = new Vertex(id,name);
        vertices.add(vertex);
        //System.out.println("ID:" +  vertex.getID() + "Name:" + vertex.getName());
    }
    public void addEdge(double weight, Vertex vertex1, Vertex vertex2, String extra) {
        Edge edge = new Edge(weight,vertex1,vertex2,extra);
        edges.add(edge);        
    }
    public void printVertices() {
        for(Vertex vertex : vertices){
               System.out.println("ID:" + vertex.getID() + " Name:" + vertex.getName());
            }   
    }
    public void printEdges() {
        for(Edge edge : edges){
               System.out.println("StartVertex:" + edge.getStartVertex() +" EndVertex:" + edge.getTargetVertex()+ "Weight:" + edge.getWeight());
            }

    }
    public Vertex getVertex(Vertex v) {
        return v;
    }
     public Map<Vertex, Double> getNeighbours(Vertex vertex) {
         Map<Vertex,Double> neighbors = new HashMap();

         Object[] check = edges.toArray();

         for(int i = 0; i < edges.size(); i++) {
            if(((Edge) check[i]).getStartVertex().getID() == vertex.getID()) {
                neighbors.put(((Edge) check[i]).getTargetVertex(),((Edge) check[i]).getWeight());
            }
            else if(((Edge) check[i]).getTargetVertex().getID() == vertex.getID()) {
                neighbors.put(((Edge) check[i]).getStartVertex(),((Edge) check[i]).getWeight());
            }
         }
        return neighbors; 
     }
}

边缘

public class Edge {

    private double weight;
    private Vertex startVertex;
    private Vertex targetVertex;
    private String extra;

    public Edge(double weight, Vertex startVertex, Vertex targetVertex, String extra) {
        this.weight = weight;
        this.startVertex = startVertex;
        this.targetVertex = targetVertex;
        this.extra = extra;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double 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;
    }
    public String getExtra() {
        return extra;
    }
    public void setExtra(String extra) {
        this.extra = extra;
    }
}

顶点

public class Vertex implements Comparable<Vertex> {

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

    public Vertex(int ID, String name) { //(Int ID, String name)?
        this.ID = ID;
        this.name = name;
        this.adjacenciesList = new ArrayList<>();
    }

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

    public String getName() {
        return name;
    }

    public void setID(int ID) {
        this.ID = ID;
    }

    public int getID() {
        return ID;
    }

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

主要

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        ReadInput graphReader = new ReadInput();
        Graph graph = graphReader.readFromStream();
        Vertex source = graphReader.calculatesSource();
        Vertex destination = graphReader.calcualteDestination();

        //graph.printEdges();    
        //graph.printVertices();

        ShortestPathFinder finder = new ShortestPathFinder();
        Optional<Path> possiblePath = finder.findShortestPath(graph,source,destination);
        if(possiblePath.isPresent() == false) {
            System.out.println("No path found");
        }
        else {
             System.out.println("Shortest path:");
             finder.getPath();
        }
    }
}

ReadInputIn

public class ReadInput {
    Vertex[] vertex = new Vertex[25252];
    final String DELIMITER = ",";
    int indexVertex = 0;

    //public Vertex[] readVertices() throws NumberFormatException, IOException {
    public Graph readFromStream() throws NumberFormatException, IOException {
         Graph graph = new Graph();
         //25252 number of elements in Place.txt file   

        //Delimiter used in CSV file
            String line = "";
            //Create the file reader
            BufferedReader fileReader = new BufferedReader(new FileReader("Place.txt"));
            String IDString = null;
            String name = null;
            int ID = 0;
            //Read the file line by line
            while ((line = fileReader.readLine()) != null) 
            {
                //Get all tokens available in line
                String[] tokens = line.split(DELIMITER);
                //for(String token : tokens)
                //{
                     IDString = tokens[0];
                     name = tokens[1];
                     ID = Integer.parseInt(IDString);
                //}
                 vertex[indexVertex] = new Vertex(ID,name);

                 graph.addVertex(ID,name);
                //System.out.println(indexVertex +":" + vertex[indexVertex].getID());
                indexVertex++;
            }
            fileReader.close();
            //return vertex;        
    //}
    //public Edge[] readEdges() throws NumberFormatException, IOException {
        Edge[] edge = new Edge[127807];
        int indexEdge = 0; 
        String line2 = "";
        BufferedReader fileReader2 = new BufferedReader(new FileReader("Road.txt"));
        String valueString = null;
        String vertex1IDName = null;
        String vertex2IDName = null;
        String extra = null;
        float value = 0;
        int vertex1ID = 0;
        int vertex2ID = 0;
        //Read the file line by line
        while ((line2 = fileReader2.readLine()) != null) 
        {
            //Get all tokens available in line
            String[] tokens2 = line2.split(DELIMITER);
            //for(String token1 : tokens2)
            //{
                vertex1IDName = tokens2[0];
                vertex2IDName = tokens2[1];
                valueString = tokens2[2];
                if(tokens2.length - 1 == 3) {
                    extra = tokens2[tokens2.length - 1];
                }
                else {
                    extra = "";
                }
                vertex1ID = Integer.parseInt(vertex1IDName);
                vertex2ID = Integer.parseInt(vertex2IDName);
                value = Float.parseFloat(valueString);

                //graph.addEdge(value, vertex1ID, vertex2ID, extra);

            //}
            //System.out.println("value: "+ value + " vertex1ID:"+ vertex1ID +" vertex2ID:"+ vertex2ID+ " extra:" + extra);
            //if vertex 1 name or vertex 2 name in vertex.getID()
            for(int i = 0; i< indexVertex; i++) {
                if(vertex1ID == vertex[i].getID() || vertex2ID == vertex[i].getID()){
                    for(int j = 0; j< indexVertex; j++) {
                        if(vertex2ID == vertex[j].getID() || vertex1ID == vertex[j].getID())  {
                            //vertex[i].addNeighbour(edge[indexEdge] = new Edge(value,vertex[i],vertex[j],extra));
                            graph.addEdge(value, vertex[i], vertex[j], extra); //newline for constructing graph
                            //System.out.println("Edge added: "+ vertex1ID +" = " + vertex[i].getID() + "   "+ vertex2ID + " = " + vertex[j].getID());
                            indexEdge++;
                        }   
                    }
                }
            }        
        }
        fileReader2.close();
        return graph;
        //return edge;
    }
    public Vertex calcualteDestination() {

        Scanner scanUserInput = new Scanner(System.in);
        System.out.println("Enter the Destination Name:");
        String destinationName = scanUserInput.nextLine();
        scanUserInput.close();

         Vertex Destination = new Vertex(0,null);

       for(int i = 0; i<indexVertex; i++) {
           if(destinationName.equals(vertex[i].getName())){
               Destination.setID(vertex[i].getID());
               Destination.setName(vertex[i].getName());    
           }
       } 
        return Destination;
    }

    public Vertex calculatesSource() {
        Scanner scanUserInput = new Scanner(System.in);  
        System.out.println("Enter the Source Name:");
        String sourceName = scanUserInput.nextLine();

        Vertex Source = new Vertex(0, null);

        for(int i = 0; i<indexVertex; i++) {
            if(sourceName.equals(vertex[i].getName())){
                Source.setID(vertex[i].getID());
                Source.setName(vertex[i].getName());    
            }
        }   

        return Source;
    }


}

Answer 1

我对您如何考虑重组代码以使其更易于调试有一些建议:

• 您当前正在存储顶点的最短路径信息。这不是一个好的设计。更好的办法是将图上的信息与最短路径上的 volatile 信息分开(并且不可变 - 即没有 setter )。
• 您应该有一个 Graph 类，它保存所有顶点和边集，并仅公开用于查询图的方法。您应该能够在输入后独立测试图形是否按预期设置，而无需测试最短路径算法
• 路径信息应封装在 ShortestPath 类中 - 无需在类外部公开该信息。您应该能够独立于代码进行单元测试来读取图表
• main 方法中的大部分逻辑应该位于单独的类中，例如 GraphReader - 这些应该是可单元测试的

我建议您进行这些更改 - 我相信以这种方式重组代码将使问题更加明显。

<小时/>

这是一个可能的设计，可以让您对我所说的内容有一些想法。

class Vertex {
    private final int id;
    private final String name;
}

class Edge {
    private final Vertex vertex1;
    private final Vertex vertex2;
    private final double weight;
}

class Graph {
    private final Set<Vertex> vertices;
    private final Set<Edge> edges;

    public void addVertex(int id, String name) {...}
    public void addEdge(int vertex1, int vertex2, double weight) {...}
    public Vertex getVertex(int id) {...}
    public Map<Vertex,Double> getNeighbours(Vertex vertex) {...}
}

class GraphReader {
    public Graph readFromStream(InputStream input) {...}
}

class Path {
    private final List<Vertex> steps;
}

这意味着您可以将构建最短路径时需要保存的临时信息封装到单独的类中:顶点和边不需要保存该信息。

class ShortestPathFinder {
    private final Graph graph;
    private final Vertex start;
    private final Vertex end;
    private final Map<Vertex,Double> minimumWeightToVertices;
    private final Map<Vertex,Vertex> previousVertex;
    private final Set<Vertex> visited;

    public ShortestPathFinder(Graph graph, int start, int end) {
        this.graph = graph;
        this.start = graph.getVertex(start);
        this.end = graph.getVertex(end);

        ...
    }

    public boolean hasPath() {...}
    public Path getPath() {...}
}

public static void main(String[] args) {
    GraphReader graphReader = new Graph();
    Graph graph = graphReader.readFromStream(System.in);
    ShortestPathFinder finder = new ShortestPathFinder(graph, 1, 10);
    if (finder.hasPath())
        System.out.println("Shortest path " + finder.getPath());
}