實現方法找到最短路徑（Dijkstra算法）的被陷在環路

這是我的，我創建找到兩個村莊之間的最短路徑方法的代碼。問題在於while循環永遠不會結束，因爲if語句中的條件從不出現if(alt < villageCost[v])。請幫我弄清楚爲什麼！實現方法找到最短路徑（Dijkstra算法）的被陷在環路

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; 

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

    villageCosts[s.getVillageName()] = 0; 
    System.out.println("This is the counter before the while loop: " +counter); 
    while(counter > 0){ 
      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++){ 
      if (mincost < villageCosts[i]){ 
       mincost = villageCosts[i]; 
       minindex= i; 
       wasVisited[i]= true; 
       counter--; 
       } 
      shortestPath.add(villages.get(i)); 
      } 

     if minimum cost in villegeCost is still infinity 
     if(villageCosts[minindex] == Integer.MAX_VALUE){ 
      System.out.println("No path exists."); 
      return null; 
      } 

    ArrayList<Road> connectingToMinIndex= villages.get(minindex).getConnectingRoads(); 
for(int i=0; i< connectingToMinIndex.size(); i++){ //roads connecting min index village 
for(int j=0; j < villages.get(minindex).getConnectingRoads().size(); j++){ 
for (int k = 0; k < villages.get(i).adjVillages.size(); k++){ 
     int v= villages.get(i).adjVillages.get(k).getVillageName(); 
     int alt= villageCosts[minindex] + villageCosts[i]; 
      if (alt < villageCosts[v]){ 
       villageCosts[v] = alt; 
       wasVisited[v]= true; 
       counter--; 
      } shortestPath.add(villages.get(alt)); 
        } 
       } 
      } 
     } //ends while loop 
     return shortestPath; 
    }

來源

2013-08-03 user2647644

啊。那麼這必須是最長的路徑算法。 –

根據你的代碼，'s.getVillageName（）'返回一個int？這是真的？這是非常具有誤導性的。 – supersam654

根據您的發佈代碼，源和圖參數沒有區別。兩個論點都是一樣的（村莊），沒有村莊。此外在村莊[s.getVillageName（）] = 0; 您應該使用源名稱將其成本設置爲零。 –