Dijkstra在Java源和目标中的算法

Question

我试图使用Dijkstra的算法来找到图中两个节点之间的最短路径。

我应该怎样做以下代码来停止计算何时发现源和目标之间的最短路径？

public void calculate(Vertex source){ 
    // Algo: 
    // 1. Take the unvisited node with minimum weight. 
    // 2. Visit all its neighbours. 
    // 3. Update the distances for all the neighbours (In the Priority Queue). 
    // Repeat the process till all the connected nodes are visited. 

    source.minDistance = 0; 
    PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>(); 
    queue.add(source); 

    while(!queue.isEmpty()){ 

     Vertex u = queue.poll(); 

     for(Edge neighbour:u.neighbours){ 
      Double newDist = u.minDistance+neighbour.weight; 

      if(neighbour.target.minDistance>newDist){ 
       // Remove the node from the queue to update the distance value. 
       queue.remove(neighbour.target); 
       neighbour.target.minDistance = newDist; 

       // Take the path visited till now and add the new node.s 
       neighbour.target.path = new LinkedList<Vertex>(u.path); 
       neighbour.target.path.add(u); 

       //Reenter the node with new distance. 
       queue.add(neighbour.target);      
      } 
     } 
    } 
} 

Answer 1

我应该做下面的代码停止计算时，如果发现源和目标之间的 最短路径

您可以在中间，因为没有“破发”在算法结束之前，您无法确定是否没有比您找到的路径更短的路径。