我正在尝试实现 Dijkstra 算法来找到图中两个交点(顶点)之间的最短路径。不幸的是,我在 while 循环中遇到了一个无限循环,我真的不知道为什么。
NodeDist 是交集和双精度之间的哈希图,用于查找图中节点之间的距离。距离由图中“街道”(边)的长度决定。Previous是一个hashmap,它跟踪交叉点到交叉点,即在我们现在查看的交叉点之前查看过的交叉点。
public List<IntersectionI> dijkstraPath(IntersectionI start, IntersectionI end){
ArrayList<IntersectionI> path = new ArrayList<IntersectionI>();
Iterator<IntersectionI> it = graph.myGraph.keySet().iterator();
//Initializing all unvisited node distances as infinity.
while (it.hasNext()){
IntersectionI next = it.next();
nodeDist.put(next, INFINITY);
}
//Remove the start node, put in 0 distance.
nodeDist.remove(start);
nodeDist.put(start, (double) 0);
queue.add(start);
//computes paths
while (!queue.isEmpty()){
IntersectionI head = queue.poll();
if (nodeDist.get(head) == INFINITY)
break;
visited.put(head, true);
List<StreetI> str = head.getStreetList();
for (StreetI e : str){
Point pt1 = e.getFirstPoint();
Point pt2 = e.getSecondPoint();
IntersectionI p1 = graph.pointGraph.get(pt1);
IntersectionI p2 = graph.pointGraph.get(pt2);
if (head.getLocation().equals(p1)){
double dist = e.getDistance();
double addedDist = nodeDist.get(start)+dist;
double p2Dist = nodeDist.get(p2);
if (addedDist < p2Dist){
previous.put(p2, head);
Point p22 = p2.getLocation();
p22.setCost(addedDist);
nodeDist.put(p2, addedDist);
queue.add(p2);
}
}
else {
double dist = e.getDistance();
double addedDist = nodeDist.get(start)+dist;
if (addedDist < nodeDist.get(p1)){
previous.put(p1, head);
Point p11 = p1.getLocation();
p11.setCost(addedDist);
nodeDist.put(p1, addedDist);
queue.add(p1);
}
}
}
}
//gets shortest path
for (IntersectionI vertex = end; vertex != null; vertex = previous.get(vertex))
path.add(vertex);
System.out.println("ya");
Collections.reverse(path);
return path;
}
//The comparator that sorts by intersection distance.
public class distCompare implements Comparator<IntersectionI> {
@Override
public int compare(IntersectionI x, IntersectionI y) {
Point xPo = x.getLocation();
Point yPo = y.getLocation();
if (xPo.getCost() < yPo.getCost())
return 1;
else if (yPo.getCost() < xPo.getCost())
return -1;
else return 0;
}
}