java - 为什么Dijkstra的这种实现不起作用？

这是我为实现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;
}

最佳答案

此行应更改

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

相反，您应该找到最低的mincost。它应该是

if (mincost >= villageCosts[i]){

编辑
回复评论

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

关于java - 为什么Dijkstra的这种实现不起作用？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18034020/