Dijkstra算法无向图的错误实现

Question

我正在尝试使用此伪代码实现Dijkstra算法以找到从无向加权图中的起始顶点到每个其他顶点的最短路径：

Initialize D(v) = 0 and D(u) = ∞ for u != v
Initialize priority queue Q of vertices using D as key.
while Q is not empty do

u = Q.removeMin()
for each vertex z adjacent to u and in Q do

if  D(u) + w((u, z)) < D(z) then

    D(z) = D(u) + w((u, z))

    update z in Q

return D

从这里：http://www.csl.mtu.edu/cs2321/www/newLectures/30_More_Dijkstra.htm

这是它的实现：

public void Dijkstra(int start) {
        int[] D = new int[E.length];
        for (int i = 0; i < E.length; i++) {
            D[i] = Integer.MAX_VALUE;
        }
        D[start] = 0;
        PriorityQueue<Integer> Q = new PriorityQueue<>();
        Q.add(start);
        while (!Q.isEmpty()) {
            Integer u = Q.poll();
            System.out.println(u + " ");
            for (int z = 0; z < E[u].size(); z++) {
                Edge e = E[u].get(z);
                if ((D[u] + e.w) < D[e.v]) {
                    D[e.v] = D[u] + e.w;
                    Q.add(e.v);
                }
            }
        }
        System.out.println(D[E.length - 1]);
    }

使用邻接列表来实现该图，并且在代码D（u）中，距离u来自v，E.length是邻接列表的长度，w是边的权重。对于此示例：5个顶点，6个边和顶点对，边的权重为0 1 20,0 2 20,0 4 40,1 3 50,2 3 30和3 4 70.输出，从1应该是：1 0 2 3 4，距离140，但我的实现产生输出：1 3 4，距离120.我的问题是为什么我得到这个答案而不是我的实现的正确答案。如果需要课程的其他部分，我会发布它们。感谢阅读和帮助！

Answer 1

我想你并不是在寻找所有的联系。例如，您有0 1个边，因此您应该添加1 0个边来设置。