java - 无向图的Dijkstra算法错误实现
问题描述
我正在尝试实现 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。我的问题是为什么我得到这个答案而不是我的实现的正确答案。如果需要课程的其他部分,我会发布它们。感谢阅读和帮助!
解决方案
我认为你并没有寻找所有的联系。例如,您有 0 1 边,因此您应该添加 1 0 边来设置。
推荐阅读
- amazon-web-services - 如何根据日期获取条目?
- java - 调用 shutdownNow 后 ScheduledExecutorService 停止可运行
- sql-server - SSIS - 如何从 SSIS 中的文件中传递良好的记录,而不是由于记录不良而使包失败
- javascript - 尝试为测试呈现反应组件时出错
- javascript - React 中的 reducer 有问题
- php - Laravel apis 无法在 https 上运行并给出错误 NET::ERR_CERT_COMMON_NAME_INVALID
- apache-spark - 如何在 Spark 中两两匹配行?
- c - 汇编中的 C while 循环
- firebase - Flutter Web:未捕获(承诺)错误:[cloud_firestore/unknown] NoSuchMethodError:null 上的无效成员:'includeMetadataChanges'
- google-apps-script - google App Script:如何在发送电子邮件时设置条件规则?