0

这是我为实现 Dijkstra 的最短路径算法而编写的一种方法......当我运行它时，永远不会到达第二个 for 循环，但我不知道如何解决这个问题。我知道这与将 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;
}
4

2 回答 2

1

这条线应该改变

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

应该反过来，你想找到最低的mincost。它应该是

if (mincost >= villageCosts[i]){

编辑 回复评论

如果它没有通过第二个循环，请检查villages.get(minindex). 我不确定它是什么样的dijkstra。如果它找到最短路径，我会更加惊讶。您可能应该退后一步并查看您的代码。

于 2013-08-03T14:50:39.103 回答
0

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  
}
于 2013-08-03T15:13:35.043 回答