java - Dijkstra 算法用 C++ 实现并转换为 Java

Question

请帮我解决这个问题:我正在尝试将 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 来定义成本(边缘权重)。 ( double 值非常接近整数，所以我怀疑这是导致问题的原因)。最后，它打印了父级列表，但列表中的元素始终是 _root 值。换句话说，条件 "if (cost[w] > cost[w0] + _m[w0][w])" 总是 false(这显然是错误的!)。

输出示例:

0 0 0 0 0 0 0 0 0 0 0.

我是不是错过了什么地方？我写错了吗？我试图在大约一个小时内找出这段代码中的错误，但它们看起来是一样的...

谢谢!

Answer 1

我测试了你的算法，它似乎工作得很好。我使用了 here 中的示例图 并返回了预期的结果。

示例图(和随机矩阵):

      b       d
      O-------O
     /|\      |\             0,    2,    3, 1000, 1000, 1000
   2/ | \3    | \2           2,    0,    6,    5,    3, 1000
   /  |  \   1|  \           3,    6,    0, 1000,    1, 1000
a O   |   \   |   O z     1000,    5, 1000,    0,    1,    2
   \  |6   \  |  /        1000,    3,    1,    1,    0,    4
   3\ |     \ | /4        1000, 1000, 1000,    2,    4,    0
     \|      \|/
      O-------O
      c       d

父级输出:

0 0 0 4 2 3

另请参阅此 short demo .

根据以上事实，您的输入一定有问题(_m)。