java - Dijkstra 算法打印最近的前驱路径而不是最短路径
问题描述
目前,我的打印功能打印最近访问的节点到目的地的路径,而不是最短路径。例如,如果最短路径是 a,c,e ,a = 1 c = 1, e = 4,另一条路径是 a,d,e 权重 a = 1, d = 4, e = 4,我的算法朝这个方向移动:a,c,d,e 但会打印 ade,因为最近访问了这些,并且我的 setPredecessor() 方法设置为一个坏的前任。对此的任何想法都会非常感激,无论是修复我当前的代码还是以不同的方式尝试。
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();
public void findShortestPath(Graph graph, Vertex source, Vertex destination, ReadInput graphReader) {
this.destination = destination;
this.source = source;
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() || edge.getStartVertex().getID() == destination.getID()) {
System.out.println("Destination found");
destination.setPredecessor(actualVertex);
destination.setDistanceFromSource(actualVertex.getDistanceFromSource() + edge.getWeight());
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);
}
}
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;
}
}
解决方案
推荐阅读
- google-apps-script - 如何在饼图中显示值 - Google Apps 脚本
- python-3.x - Pandas:如何计算 DateTime 索引
- nginx - Nginx 2 重写 2 例
- javascript - 导航栏不展开(React JS)
- reactjs - 样式(css)不适用于阴影 DOM 中的 React 应用程序
- regex - 替换为 regexp i Template Toolkit
- sparql - RDFlib 空白节点更新查询
- javascript - InfoWindow 上的按钮事件
- python - 评估从 keras 加载的 hdf5 文件
- bash - 由于 awk 列提取而导致保存 bash 变量的问题