루프에서 걸리는 최단 경로 (Dijkstra)를 찾는 방법 구현

Question

두 마을 간의 최단 경로를 찾기 위해 만든 방법에 대한 코드입니다. 문제는 if 문의 조건이 if(alt < villageCost[v])이 결코 발생하지 않기 때문에 while 루프가 끝나지 않는다는 것입니다. 이유를 알아내는 데 도움주세요!

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; 
    } 

Answer 1

디버깅하려면 while 루프 반복 횟수 제한을 설정하십시오. 그런 다음 필요에 따라 while 루프 내에서 System.out.print를 사용하여 각 반복마다 각 변수의 값을 인쇄하십시오. 설정된 반복 양이 완료되면 화면에 인쇄 된 결과를 검사하십시오. 이것이 루프를 디버깅하는 가장 좋은 방법입니다. 당신이 Integer.MAX_VALUE에 villageCosts 모든 항목을 초기화하기 때문에 (다음 0 현재 변경)

if (mincost < villageCosts[i]){ 

당신은 유사 mincost를 초기화 :

Answer 2

이것은 사실이 없을 것

int mincost = Integer.MAX_VALUE;