请帮我解决这个问题:我正在尝试将 Dijkstra 算法(由教授用 C++ 实现)翻译成 Java,但它不起作用。
int *cost = new int[numVert],
*frj = new int[numVert],
*parent = new int[numVert],
w, w0;
for (w = 0; w < numVert; w++) {
parent[w] = -1;
cost[w] = matrizAdj[_vertInicial][w];
frj[w] = _vertInicial;
}
parent[_vertInicial] = _vertInicial;
cost[_vertInicial] = 0;
while (1) {
int mincost = -1;
for (w = 0; w < numVert; w++) {
if (parent[w] != -1 || cost[w] == 0)
continue; // vert ja alcancado ou nao possui aresta com vert atual.
// se menor que mincost ou mincost == infinito
if (mincost > cost[w] || mincost == -1)
mincost = cost[w0 = w];
}
if (mincost == -1) break;
parent[w0] = frj[w0];
for (w = 0; w < numVert; w++)
if (cost[w] > cost[w0] + matrizAdj[w0][w]) {
cost[w] = cost[w0] + matrizAdj[w0][w];
frj[w] = w0;
}
}
for (w = 0; w < numVert; w++)
cout << " " << parent[w];
教授的版本工作得很好。最后,它将打印一个父节点列表,其中 parent[w] 是节点 w 的父节点。
输出示例:0 1 2 0 0 1 0 4 0 2 0。
好吧,我用Java编写了这段代码:
double mincost, cost[] = new double[_m.length];
int frj[], parent[], w0;
frj = new int[_m.length];
parent = new int[_m.length];
for (int w = 0; w < _m.length; w++) {
parent[w] = -1;
cost[w] = _m[_root][w];
frj[w] = _root;
}
parent[_root] = _root;
cost[_root] = 0;
w0 = 0;
while (true) {
mincost = -1;
for (int w = 0; w < _m.length; w++) {
if (parent[w] != -1 || cost[w] == 0) {
continue;
}
if (mincost > cost[w] || mincost == -1) {
mincost = cost[w0 = w];
}
}
if (mincost == -1) {
break;
}
parent[w0] = frj[w0];
for (int w = 0; w < _m.length; w++) {
if (cost[w] > cost[w0] + _m[w0][w]) {
cost[w] = cost[w0] + _m[w0][w];
frj[w] = w0;
}
}
}
for (int i = 0; i < parent.length; i++) {
System.out.print(" " + parent[i]);
}
这基本上是一样的,除了我的版本使用 double 来定义成本(边缘权重)。(双精度值非常接近整数,所以我怀疑这是导致问题的原因)。最后,它打印出父列表,但列表中的元素始终是_root
值。换句话说,条件"if (cost[w] > cost[w0] + _m[w0][w])"
总是false
(这显然是错误的!)。
输出示例:
0 0 0 0 0 0 0 0 0 0 0.
我错过了这里的一些地方吗?我是不是写错了什么?我试图在这个代码中找到大约一小时的错误,但它们看起来一样......
谢谢!