从前辈打印 Dijkstra 算法
Printing Dijkstra Algorithm from predecessors
我正在尝试打印 Dijkstra 算法,但目前只有目标 ID 从我的 getPath() 方法打印。我的想法是从目标顶点向后工作并打印每个前导,直到打印起始顶点。如果有另一种方法 store/print 我愿意尝试不同的方法,我很感激任何想法!
class ShortestPathFinder {
private Graph graph = new Graph();
private Vertex source = new Vertex(0, null);
private Vertex destination = new Vertex(0,null);
private Map<Vertex,Vertex> previousVertex = new HashMap();
private Set<Vertex> visited = new HashSet();
public Optional<Path> findShortestPath(Graph graph, Vertex source, Vertex destination, ReadInput graphReader) {
this.destination = destination;
this.source = source;
Optional<Path> pathFound = Optional.empty();
source.setDistanceFromSource(0);
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
priorityQueue.add(source);
source.setVisited(true);
boolean destinationFound = false;
while( !priorityQueue.isEmpty() && destinationFound == false){
// Getting the minimum distance vertex from priority queue
Vertex actualVertex = priorityQueue.poll();
System.out.println("working on: " + actualVertex.getID());
actualVertex = graphReader.SetAdjList(actualVertex);
for(Edge edge : actualVertex.getAdjacenciesList()){
Vertex v = edge.getTargetVertex();
System.out.println("a Neighbor is: " + v.getID());
if(!v.isVisited()) {
if(v.getID() == destination.getID()) {
System.out.println("Destination found");
Path path = new Path(previousVertex);
pathFound = Optional.of(path);
destinationFound = true;
break;
}
double newDistance = actualVertex.getDistanceFromSource() + edge.getWeight();
if( newDistance < v.getDistanceFromSource() ){
priorityQueue.remove(v);
v.setDistanceFromSource(newDistance);
v.setPredecessor(actualVertex);
priorityQueue.add(v);
System.out.println("Added: " + v.getID());
}
}
}
actualVertex.setVisited(true);
}
return pathFound;
}
public List<Vertex> getPath() {
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=destination;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
return path;
}
}
到达目的地时调用代码中的以下部分:
if(v.getID() == destination.getID()) {
System.out.println("Destination found");
Path path = new Path(previousVertex);
pathFound = Optional.of(path);
destinationFound = true;
break;
}
相应的 v 从来没有设置其前身,这是您的 getPath()
方法所依赖的。考虑在 if 语句中设置它,如下所示:
if(v.getID() == destination.getID()) {
System.out.println("Destination found");
destination.setPredecessor(actualVertex); // sets the predecessor for backwards traversal
Path path = new Path(previousVertex);
pathFound = Optional.of(path);
destinationFound = true;
break;
}
我正在尝试打印 Dijkstra 算法,但目前只有目标 ID 从我的 getPath() 方法打印。我的想法是从目标顶点向后工作并打印每个前导,直到打印起始顶点。如果有另一种方法 store/print 我愿意尝试不同的方法,我很感激任何想法!
class ShortestPathFinder {
private Graph graph = new Graph();
private Vertex source = new Vertex(0, null);
private Vertex destination = new Vertex(0,null);
private Map<Vertex,Vertex> previousVertex = new HashMap();
private Set<Vertex> visited = new HashSet();
public Optional<Path> findShortestPath(Graph graph, Vertex source, Vertex destination, ReadInput graphReader) {
this.destination = destination;
this.source = source;
Optional<Path> pathFound = Optional.empty();
source.setDistanceFromSource(0);
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
priorityQueue.add(source);
source.setVisited(true);
boolean destinationFound = false;
while( !priorityQueue.isEmpty() && destinationFound == false){
// Getting the minimum distance vertex from priority queue
Vertex actualVertex = priorityQueue.poll();
System.out.println("working on: " + actualVertex.getID());
actualVertex = graphReader.SetAdjList(actualVertex);
for(Edge edge : actualVertex.getAdjacenciesList()){
Vertex v = edge.getTargetVertex();
System.out.println("a Neighbor is: " + v.getID());
if(!v.isVisited()) {
if(v.getID() == destination.getID()) {
System.out.println("Destination found");
Path path = new Path(previousVertex);
pathFound = Optional.of(path);
destinationFound = true;
break;
}
double newDistance = actualVertex.getDistanceFromSource() + edge.getWeight();
if( newDistance < v.getDistanceFromSource() ){
priorityQueue.remove(v);
v.setDistanceFromSource(newDistance);
v.setPredecessor(actualVertex);
priorityQueue.add(v);
System.out.println("Added: " + v.getID());
}
}
}
actualVertex.setVisited(true);
}
return pathFound;
}
public List<Vertex> getPath() {
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=destination;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
return path;
}
}
到达目的地时调用代码中的以下部分:
if(v.getID() == destination.getID()) {
System.out.println("Destination found");
Path path = new Path(previousVertex);
pathFound = Optional.of(path);
destinationFound = true;
break;
}
相应的 v 从来没有设置其前身,这是您的 getPath()
方法所依赖的。考虑在 if 语句中设置它,如下所示:
if(v.getID() == destination.getID()) {
System.out.println("Destination found");
destination.setPredecessor(actualVertex); // sets the predecessor for backwards traversal
Path path = new Path(previousVertex);
pathFound = Optional.of(path);
destinationFound = true;
break;
}