0

这是我创建的用于查找两个村庄之间最短路径的方法的代码。问题是 while 循环永远不会结束，因为 if 语句中的条件if(alt < villageCost[v])永远不会发生。请帮我找出原因！！

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

2 回答 2

1

这永远不会是真的：

if (mincost < villageCosts[i]){

因为您将所有villageCosts项目初始化为 Integer.MAX_VALUE（然后将当前更改为0）并且您进行了mincost类似的初始化：

int mincost = Integer.MAX_VALUE;
于 2013-08-03T04:42:23.930 回答
0

要进行调试，请对 while 循环的迭代次数设置限制。然后在 while 循环内任何需要的地方使用 System.out.print 在每次迭代时打印每个变量的值。完成设定的迭代次数后，检查打印到屏幕上的结果。这是调试循环的最佳方式。

于 2013-08-03T02:13:22.423 回答