CODEWITHSUNDEEP
javaloopsdijkstra
user2647644
user2647644

Reputation: 1

implementation of method to find a shortest path (Dijkstra) getting stuck in loop

This is my code for a method that I created to find the shortest path between two villages. The problem is that the while loop never ends, because the condition in the if statement if(alt < villageCost[v]) never occurs. Please help me figure out why!!

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

Upvotes: 0

Views: 531

Answers (2)

akf
akf

Reputation: 39485

this will never be true:

if (mincost < villageCosts[i]){

because you initialize all of your villageCosts items to Integer.MAX_VALUE (and then change the current to 0) and you initialize mincost similarly:

int mincost = Integer.MAX_VALUE;

Upvotes: 1

user2593666
user2593666

Reputation:

To debug, set a limit on how many times your while loop iterates. Then use System.out.print wherever necessary inside the while loop to print the value of each variable at each iteration. Examine the results printed to your screen after your set amount of iterations have completed. That's the best way to debug loops.

Upvotes: 0

Related Questions