java - Dijkstra算法java实现bug

Question

所以首先这是硬件，所以尽量不要马上给我答案，但我在编写 Dijstra 算法时遇到了问题。该实验室让我们构建了一个优先级队列，我已经完成并通过了给定的 JUnit 测试，所以我认为它是正确的。实验的第二部分让我们在 dijstra 算法的实现中使用队列。这是我的 Dijkstra 代码

/**
 * Compute shortest paths in a graph.
 *
 * Your constructor should compute the actual shortest paths and
 * maintain all the information needed to reconstruct them.  The
 * returnPath() function should use this information to return the
 * appropriate path of edge ID's from the start to the given end.
 *
 * Note that the start and end ID's should be mapped to vertices using
 * the graph's get() function.
 */

class ShortestPaths {

    Multigraph graph;
    final int INF = Integer.MAX_VALUE;
    PriorityQueue<Integer> Q;
    int n;
    int dist[];
    Handle handles[];
    Edge edge[];

    /**
     * Constructor
     */
    public ShortestPaths(Multigraph G, int startId) {
        Q = new PriorityQueue<Integer>();
        graph = G;
        n = graph.nVertices();
        dist = new int [n];
        edge = new Edge [n];
        handles = new Handle[n];

        for (int i = 0; i<n; i++){
            dist[i] = INF;
        }
        dist[startId] = 0;

        Handle h = Q.insert(startId, dist[startId]);
        handles[startId] = h;   
        Q = new PriorityQueue<Integer>();
        while (!Q.isEmpty()){
            Vertex v = graph.get(Q.min());
            Q.extractMin();
            while (v.adj().hasNext()){
                relax(v.adj().next());  
            }       
        }   
    }

    private void relax(Edge e) {
        Handle h;
        int v = e.from().id();
        int w = e.to().id();
        if (dist[w] > dist[v] + e.weight()) {
            dist[w] = dist[v] + e.weight();
            edge[w] = e;
            if (handles[w].getIndex() != -1){
                Q.decreaseKey(handles[w], dist[w]);
            }
            else{
                h = Q.insert(w, dist[w]);
                handles[w] = h;
            }
        }
    }

    /**
     * Calculates the list of edge ID's forming a shortest path from the start
     * vertex to the specified end vertex.
     *
     * @return the array
     */
    public int[] returnPath(int endId) {
        int c = 0;
        int[] path = new int[edge.length];
        for (Edge e = edge[endId]; e != null; e = edge[e.from().id()]) {
            path[c] = e.id();
            c++;
        }
        return path;
    }


}

正如您所知，句柄只是一个对象，它存储关联键值对的索引，这样我们以后就可以找到它。 handle 会自动更新，您可以在我的优先级队列中的交换过程中看到这一点。无论如何，问题是我的 edge[] 数组由于某种原因填充了 null，所以我无法返回任何路径。如何修复我的算法以正确更新 edge[]？任何帮助，将不胜感激。如果您想了解更多信息，请告诉我。如果您想查看它们，我还会发布 Vertex 和 Edge 类。

Answer 1

我注意到一个错误:

Q = new PriorityQueue<Integer>();
while (!Q.isEmpty()){ // <-- Q is always empty beсause of previous line