爲什麼Dijkstra的這個實現不起作用？

Question

這是我寫來實現Dijkstra的最短路徑算法的方法......當我運行它時，第二個for循環從來沒有達到，但我無法弄清楚如何解決這個問題。我知道它與將mincost設置爲MAX_VALUE有關，但我不知道要如何初始化。

// method to find shortest path between source village,s, and destination village, d 
public ArrayList<Village> shortestPath(Village s, Village d){ 
    int[] villageCosts= new int[villages.size()]; 
    boolean[] wasVisited= new boolean[villages.size()]; 
    shortestPath = new ArrayList<Village>(); 
    int counter= wasVisited.length; 
    System.out.println("the value of the counter is: "+ counter); 

    for(int i=0; i<villageCosts.length; i++){ //initialize to infinity 
     villageCosts[i]= Integer.MAX_VALUE; 
    } 

    //villageCosts[s.getVillageName()] = 0; while(counter > 0){ 
     System.out.println("in the while loop! the value of the counter is: "+ counter); 
     int mincost = Integer.MAX_VALUE; 
     int minindex= 0; 

     //if the minimum cost in villageCosts i still infinity 
     for(int i=0; i<villageCosts.length && wasVisited[i]==false; i++){ 
      System.out.println("in the first for loop!"); 
      if (mincost <= villageCosts[i]){ 
       System.out.println("in the first if statement!"); 
       mincost = villageCosts[i]; 
       minindex= i; 
       wasVisited[i]= true; 
       counter--; 
       System.out.println("the value of the counter after the first if statement: " + counter); 
       System.out.println("min index: " + minindex); 
      } 
      shortestPath.add(villages.get(i)); 
     } System.out.println("out of the first for loop!"); 


     //if minimum cost in villegeCost is still infinity 
     if(villageCosts[minindex] == Integer.MAX_VALUE){ 
      System.out.println("in the if statement that returns null if true!"); 
      return null; 
     } 

     //for min index road loop through adjVillages,and calculate village cost of minindex + cost of road between minindex and each adjVillage 
     for(int i=0; i< villages.get(minindex).adjVillages.size(); i++){ 
      System.out.println("in the second for loop!"); 
      Road b= getRoadBetween(villages.get(minindex), villages.get(i)); 
      int toll=b.getToll(); 
      int alt= villageCosts[minindex] + toll; 
      if(alt < toll){ 
       System.out.println("in the if statement in the second for loop!"); 
       toll=alt; 
       wasVisited[toll]= true; 
       counter--; 
      } shortestPath.add(villages.get(alt)); 
     } 
    }   System.out.println("out of the while loop!"); //ends while loop 
    return shortestPath; 
} 

Answer 1

此行應改爲

int mincost = Integer.MAX_VALUE; 
if (mincost <= villageCosts[i]){ 

它應該是倒過來，你想找到最低mincost。它應該是

if (mincost >= villageCosts[i]){ 

編輯 回覆評論

如果它沒有通過第二循環運行，檢查villages.get(minindex)大小。我不確定它是什麼樣的dijkstra。如果發現最短路徑，我會更加驚訝。您應該退後一步並查看您的代碼。

Answer 2

the second for loop is never reached

第一循環後if條件始終是真實的，你不會覆蓋villageCosts[minindex] ...

if(villageCosts[minindex] == Integer.MAX_VALUE){ 
    System.out.println("in the if statement that returns null if true!"); 
    return null 
}