Алгоритм Dijkstra, реализованный на C++ и преобразованный в Java

Question

Пожалуйста, помогите с этой проблемой: Я пытаюсь перевести алгоритм Дейкстры (реализованный на 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. 

ли я пропустил некоторое место здесь? Я что-то написал неправильно? Я пытаюсь найти ошибку в этом коде около часа, но они выглядят одинаково ...

Спасибо!

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).