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

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 0 2

好吧，我做了这个代码在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. 

难道我错过了一些点在这里？我写错了什么？我试图在这段代码中找到大约一个小时的错误，但它们看起来一样...

谢谢！

Answer 1

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

样品曲线图（和矩阵ajducency）：

 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）。