0

これは、Dijkstra の最短パス アルゴリズムを実装するために私が書いたメソッドです...実行すると、2 番目の 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]){

コメントへの返信を編集

2 番目のループを通過しない場合は、 のサイズを確認しますvillages.get(minindex)。どんな種類のダイクストラかはわかりません。最短経路を見つけたら、さらに驚くでしょう。おそらく、一歩下がってコードを確認する必要があります。

于 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 に答える