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 条边来设置。