Dijkstra的算法Java：总是增加最后一条边，而不是最短边

Question

我有一个要到达的顶点，称为目的地。目前，我的算法似乎已超过该顶点。

似乎总是添加了要测试的最短距离的最后一条边。我不确定这是否是由于我的算法错误或我如何添加邻居，但我一直在尝试同时测试两者。

有时添加最后两个边缘，例如：

ID：39330值：1.309999942779541

ID：39360值：1.940000057220459

ID：39374值：1.9700000286102295

添加：39360添加：39374

或仅添加最后一个：

ID：39347值：1.2999999523162842

ID：24955值：2.5799999237060547

添加：24955

非常感谢任何想法，建议或想法！

[Graph

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() + "ID: "+ edge.getStartVertex().getID() +" EndVertex:" + edge.getTargetVertex()+"ID: "+ edge.getTargetVertex().getID() + "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();
         Object[] check2 = vertices.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());
            }
            //check for 
            /*else if(((Edge) check[i]).getTargetVertex() == vertex) {
                neighbors.put(((Edge) check[i]).getStartVertex(),((Edge) check[i]).getWeight());
            }*/
         }
         for (Entry<Vertex, Double> entry : neighbors.entrySet()) {
                System.out.println("ID: " + entry.getKey().getID() +  " Value: " + entry.getValue() );
            }
        return neighbors; 
     }
}

ShortestPathFinder] >>

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Set;

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(actualVertex);
        //find Neighbor with lowest weight
          for(Entry<Vertex, Double> neighbor : neighbors.entrySet()){             
                 Vertex v = neighbor.getKey();
                if(v.getID() == destination.getID()) {
                    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());
        }
    }
}
[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;
    }
}
[顶点

] >>

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

                //adds all edges with null vertex names, need to account for edges that connect to actual vertices?
                Vertex vertex1 = new Vertex(vertex1ID,"null");
                Vertex vertex2 = new Vertex(vertex2ID,"null");

                graph.addEdge(value,vertex1, vertex2, extra);  
        }
        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;
    }   
}
[Main] >>
ppublic 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();
        }
    }
}
我有一个要到达的顶点，称为目的地。目前，我的算法似乎已经超过了该顶点。似乎总是添加了要测试最短距离的最后一条边。 ... 
[找到路径后应立即返回pathFound。
if (v.getID() == destination.getID()) {
    ...
    return Optional.of(path);
}
否则，您不仅在浪费时间探索图的其余部分，而且甚至可能找到到目标的另一条longer
路径，并用该路径覆盖最短路径。
在这一点上，path只是new Path()也有点奇怪。似乎您仅使用此选项将Optional标记为非空，而在ShortestPathFinder的previousVertex映射中保留了有关路径的实际信息。最好将路径信息直接放入Path对象中，以与在getPath中类似的方式展开。

Answer 1

[找到路径后应立即返回pathFound。

if (v.getID() == destination.getID()) {
    ...
    return Optional.of(path);
}

否则，您不仅在浪费时间探索图的其余部分，而且甚至可能找到到目标的另一条longer