Dijkstra算法中的無限循環？

我試圖實現Dijkstra算法來查找圖中兩個交點（頂點）之間的最短路徑。不幸的是，我在while循環中得到了一個無限循環，我無法弄清楚爲什麼。Dijkstra算法中的無限循環？

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; 

    } 
}

來源

2012-12-11 user202925

在哪個循環？你有沒有試過用小圖調試？在while循環中的 –

。 – user202925

做街道走兩邊？在列表中是a-> b，並且b-> a？它看起來像我可以得到兩個，每個迭代只會添加另一個？ - 更新不是這樣的情況，因爲你有一個<（不是<=） –

所以，這結束瞭解決的意見問題：

double addedDist = nodeDist.get(start)+dist;

應該

double addedDist = nodeDist.get(head)+dist;

兩次。

增加的距離應該來自當前頂點，而不是起始頂點（距離爲0）。

來源

2012-12-11 01:12:35 irrelephant

Dijkstra算法中的無限循環？

回答

相關問題