Как напечатать полный путь алгоритма Дейкстры в Java

Question

В настоящее время печатается только последняя вершина, и минимальное расстояние кажется равным бесконечности. Я не могу найти, где проблема с тем, что вершина не добавляется в ArrayList с «кратчайшим путем». Я хотел бы также распечатать все края, которые взяты пути. Любые предложения приветствуются. Ниже приведен мой полный код, спасибо!

Редактировать : я отредактировал свои классы в соответствии с рекомендациями sprinter.

Ошибка в моем классе Graph, в моем методе getNeighbours (). Информация об источнике добавляется в качестве соседа, хотя я пытаюсь получить его соседей.

Я также не уверен, как распечатать информацию о ребре вместе с информацией о вершине.

Любые рекомендации приветствуются!

ShortestPathFinder

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

Edge

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

Vertex

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

У меня есть несколько предложений о том, как вы можете подумать о реструктуризации вашего кода, чтобы облегчить отладку:

• В настоящее время вы храните информацию о кратчайшем пути вместе с вершиной. Это не хороший дизайн. Лучше было бы иметь информацию на графике отдельно (и неизменной - то есть без сеттеров) от изменчивой информации о кратчайших путях.
• У вас должен быть класс Graph, который содержит все наборы вершин и ребер и предоставляет только методы для опроса графа. Вы должны быть в состоянии выполнить модульное тестирование того, что график настроен так, как вы ожидаете, после ввода независимо от тестирования алгоритма кратчайшего пути
• Информация о пути должна быть инкапсулирована в вашем классе ShortestPath - не должно быть необходимости выставлять что вне класса. Вы должны быть в состоянии выполнить модульное тестирование независимо от кода для чтения графиков
• Большинство логик c в вашем методе main должны быть в отдельных классах, таких как GraphReader - это должны быть единицы testable

Я предлагаю вам внести эти изменения - я уверен, что реструктуризация кода таким образом сделает проблему намного более очевидной.

---

Вот возможный дизайн, чтобы дать у вас есть некоторые идеи о том, о чем я говорю.

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