CODEWITHSUNDEEP
javaloopsdijkstra
user2648788
user2648788

Reputation: 1

why is this implementation of Dijkstra's not working?

This is a method i wrote to implement Dijkstra's shortest path algorithm... when I run it, the second for loop is never reached but I can't figure out how to fix this. I know it has something to do with setting the mincost as MAX_VALUE but I don't know how else to initialize.

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

Upvotes: 0

Views: 98

Answers (2)

bsd
bsd

Reputation: 2717

This line should be changed

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

It should have been the other way round, you want to find the lowest mincost. It should be 

if (mincost >= villageCosts[i]){

Edit Reply to comment

If it does not run through the second loop, check the size of villages.get(minindex). I am not sure what kind of dijkstra it is. I would be even more surprised if it finds out the shortest path. You should probably step back and review your code.

Upvotes: 1

boxed__l
boxed__l

Reputation: 1336

the second for loop is never reached

The condition in if after the first loop is always true as you are not overwriting villageCosts[minindex]...

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

Upvotes: 0

Related Questions