Dijkstra 没有对先前的节点数组进行更改

Question

使用 Dijkstra 进行路由查找，但每次我运行算法，我最终都没有对之前的节点数组进行更改。

public static int[] findRoute(Web m, int s)
{
    final int[] dist = new int[m.edges.length];         //shortest known dist from s
    final int[] pred = new int[m.edges.length];     //previous node in path
    final boolean[] visited = new boolean[m.edges.length];  //all start as false

    //sets each distance to max, until measured
    for(int i = 0; i < dist.length; i++)
    {  
        dist[i] = Integer.MAX_VALUE;
    }
    dist[s] = 0; //distance to self is 0 always

    for(int i = 0; i < dist.length; i++)
    {
        int next = minVertex (dist, visited);
        visited[next] = true;
        //shortest path to next is dist[next] and via pred[next]
        //counts roads that are connected
        int c = 0;

        for(int j = 0; j < m.edges[next].length; j++)
        {
            if(m.edges[next][j] > 0) c++;
        }
        //create array to hold connected road indexes
        int[] n = new int[c];
        //reset c
        c = 0;
        //loop to fill n with indexes of neighbors
        for(int j = 0; j < m.edges[next].length; j++)
            {if(m.edges[next][j]>0) n[c++] = j;}
        for(int j = 0; j < n.length; j++){
            final int v = n[j];
            final int d = dist[next] + m.edges[next][v];
            if (dist[v] > d) {
                dist[v] = d;
                pred[v] = next;
            }
        }
    }
    return pred; //ignore pred[s] == 0
}

Web class 只是一个二维数组，如果存在连接，它会保存节点与节点之间的距离。经过一些测试，似乎 pred 没有在第一轮之后更新。我如何更改它以正确更新 pred 数组？这是我第一次尝试使用该算法，我已经阅读了一堆伪代码，但我一直无法弄清楚我哪里出错了。目前，当我尝试打印一条路径时，我只是得到目的地，然后是无限节点 0。

最小顶点

private static int minVertex(int[] dist, boolean[] v)
{
    int x = Integer.MAX_VALUE;
    int y = -1; //graph not connected or no unvisited
    for(int i = 0; i < dist.length; i++)
    {
        if(!v[i] && dist[i] < x) 
        {
            y = i;
            x = dist[i];
        }
    }
    System.out.println(y);
    return y;
}

边和交点

交叉点 1：X = 0，Y = -1
交叉点 2：X = 0，Y = 0
交叉点 3：X = 1，Y = 0
交叉点 4：X = 1，Y = 3
交叉点 5：X = 0，Y = 3
交叉点 6：X = 2，Y = 3

边都是500长，边是

i2-i1
i1-i2
i2-i3
i3-i4
i4-i5
i5-i2
i2-i5
i6-i4

Answer 1

您在答案中输入的代码是 O(V^2) 数组 Dijkstra 的正确实现。根据您对问题的描述，我认为问题是在您的 minVertex() 代码（您没有提供）中，您需要检查是否访问了顶点，并且只有 return 非顶点之间的最小距离-访问过的顶点。

如果这能解决问题，请告诉我。如果没有，您能否编辑您的问题以提供其余代码？

Dijkstra 没有对先前的节点数组进行更改

Dijkstra's isn't making changes to previous node array

java

dijkstra