跟踪使用DijkstraAlgorithm

Question

我在实施DijkstraAlgorithm.My代码有问题的最短路径是如下

class DijkstraAlgorithmSet { 

    private int distances[]; 
    private java.util.Set<Integer> settled; 
    private java.util.Set<Integer> unsettled; 
    private int number_of_nodes; 
    int source = 0; 
    int min; 
    int node = 0; 

    public DijkstraAlgorithmSet(int number_of_nodes) { 
     this.number_of_nodes = number_of_nodes; 
     distances = new int[number_of_nodes]; 
     settled = new java.util.HashSet<>(); 
     unsettled = new java.util.HashSet<>(); 
    } 
    List<Integer> evaluationNodeList = new ArrayList(); 
    List<Integer> destinationNodeList = new ArrayList(); 

    public void dijkstra_algorithm() { 
     int i, j; 
     int evaluationNode; 
     int distance = Integer.MAX_VALUE; 


     for (int k = 0; k < number_of_nodes; k++) { 
      distances[k] = Integer.MAX_VALUE; 
     } 

     unsettled.add(source); 
     distances[source] = 0; 
     while (!unsettled.isEmpty()) { 
      evaluationNode = getNodeWithMinimumDistanceFromUnsettled(); 
      unsettled.remove(evaluationNode); 
      settled.add(evaluationNode); 
      evaluateNeighbours(evaluationNode); 
     } 
     evaluationNodeList.add(number_of_nodes - 1); 
     Iterator<Integer> iterator = settled.iterator(); 
     while (iterator.hasNext()) { 
      Integer next = iterator.next(); 
     } 

    } 

    private int getNodeWithMinimumDistanceFromUnsettled() { 


     Iterator<Integer> iterator = unsettled.iterator(); 
     node = iterator.next(); 
     min = distances[node]; 
     System.out.println("minimum>>>>" + min); 
     for (int i = 1; i <= distances.length; i++) { 
      if (unsettled.contains(i)) { 
       if (distances[i] <= min) { 
        min = distances[i]; 
        node = i; 
       } 

      } 

     } 

     System.out.println("min>>>>" + min); 
     return node; 
    } 
    List<Integer> list=new ArrayList<>(); 
    private void evaluateNeighbours(int evaluationNode) { 
     int edgeDistance = -1; 
     int newDistance = -1; 
     int destinationNode; 
     int temp = 0; 
     for (destinationNode = 0; destinationNode < number_of_nodes; destinationNode++) { 
      if (!settled.contains(destinationNode)) { 
       if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE) { 
        edgeDistance = adjacencyMatrix[evaluationNode][destinationNode]; 
        newDistance = distances[evaluationNode] + edgeDistance; 
        if (newDistance < distances[destinationNode]) { 
         distances[destinationNode] = newDistance; 
         System.out.println("temp>>>>>" + evaluationNode); 
         temp = evaluationNode; 
         System.out.println("destinationNode>>>>>" + destinationNode); 

        } 
        unsettled.add(destinationNode); 
       } 

      } 

     } 



    } 

我wwant追踪path.But我还没有发现的路径。我只使用上面的代码得到了最后的距离。

Answer 1

您可以修改算法以在每个节点中存储最短路径中的前驱节点。 算法完成后，您可以按照前辈的原点重建路径。

换句话说有另一个数组private int predecessors[];并记住最佳的距离传来：

if (newDistance < distances[destinationNode]) { 
    distances[destinationNode] = newDistance; 
    predecessors[destinationNode] = evaluationNode; 
    ... 
}