Почему эта реализация Dijkstra не работает?

Question

Это метод, который я написал, чтобы реализовать алгоритм кратчайшего пути Dijkstra ... когда я его запускаю, второй цикл цикла никогда не достигается, но я не могу понять, как это исправить. Я знаю, что это связано с установкой 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). Я не уверен, что это за дийкстра. Я был бы еще более удивлен, если бы узнал кратчайший путь. Вероятно, вам следует отступить и просмотреть свой код.

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 
}