java - 查找卡在循环中的最短路径(Dijkstra)的方法的实现

这是我为找到两个村庄之间的最短路径而创建的方法的代码。问题是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;
    }

最佳答案

这将永远是不正确的：

if (mincost < villageCosts[i]){

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

int mincost = Integer.MAX_VALUE;

关于java - 查找卡在循环中的最短路径(Dijkstra)的方法的实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18028089/