CODEWITHSUNDEEP
javac++graphdijkstra
ldavid
ldavid

Reputation: 2552

Dijkstra algorithm implemented in C++ and converted to Java

Please, help me with this problem: I am trying to translate Dijkstra algorithm (implemented in C++ by a professor) to Java but it's not working.

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];

The professors's version is working just fine. At the end, it will print a list of parents, where parent[w] is the parent of node w.

Output example: 0 1 2 0 0 1 0 4 0 2 0.

Well, I made this code in 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]);
}

Which is basically the same thing, except that my version uses double to define costs (edge weight). (the double values are pretty close to integers, so I doubt this is causing the problem). At the end, it prints the list of parents, but the elements in the list are always the _root value. In another words, the condition "if (cost[w] > cost[w0] + _m[w0][w])" are always false (this is clearly wrong!).

Output example: 

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

Did I missed some spot here? Did I wrote something wrong? I am trying to find the error in this code about one hour, but they look the same...

Thank you!

Upvotes: 0

Views: 531

Answers (1)

gkalpak
gkalpak

Reputation: 48211

I tested your algorithm and it seems to work just fine. I used the sample graph from here and it returned the expected results.

Sample graph (and ajducency matrix): 

      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

Parents output:

0 0 0 4 2 3

See, also, this short demo.

Based on the above facts, there must be something wrong with your input (_m).

Upvotes: 2

Related Questions