Dijkstr finds no path less

Question

I’m implementing Dijkstra’s algorithm to find the shortest path on a network. Starting from a node of origin s, I need to calculate the shortest path to reach all other nodes that exist on the network. But the algorithm is not working properly.

Here’s the code? (HEU is a graph struct)

int dijkstra(GRAPHD &HEU, int s) {
HEU.d[s] = 0; 
for (int i = 1; i <= HEU.nb_nodes; i++) {
    if (i != s)
        HEU.d[i] = INT_MAX; 
}
for (int i = 1; i <= HEU.nb_nodes; i++) {
    HEU.S[i] = 0; 
    HEU.Q[i] = i; 
}

while (!vazio(HEU)) {
    int u = extract_mimimum(HEU);
    HEU.S[u] = 1;
    retira(HEU, u);
    for (int i = 1; i <= HEU.nb_nodes; i++) {
        if (HEU.qr[u][i] != -1) { //indica que existe o arco
            if (HEU.qr[u][i] != -2) { //indica que existe o arco
                if (HEU.d[HEU.qr[u][i]] > HEU.d[u] + HEU.c[u][HEU.qr[u][i]])
                    HEU.d[HEU.qr[u][i]] = HEU.d[u] + HEU.c[u][HEU.qr[u][i]];
            }
        }
    }
}


return HEU.d;
}

The problem is when it starts at node two. All distances in the matrix HEU. c[ ] [ ] are 1 and the graph looks like this:

HEU.qr[1][1] = 5;

HEU.qr[2][1] = 1;

HEU.qr[2][2] = 3;

HEU.qr[3][1] = 7;

HEU.qr[3][2] = 4;

HEU.qr[4][1] = 8;

HEU.qr[5][1] = 9;

HEU.qr[6][1] = 2;

HEU.qr[6][2] = 5;

HEU.qr[7][1] = 11;

HEU.qr[7][2] = 6;

HEU.qr[8][1] = 7;

HEU.qr[9][1] = 10;

HEU.qr[10][1] = 6;

HEU.qr[10][2] = 11;

HEU.qr[11][1] = 15;

HEU.qr[12][1] = 8;

HEU.qr[13][1] = 9;

HEU.qr[14][1] = 10;

HEU.qr[14][2] = 13;

HEU.qr[15][1] = 14;

HEU.qr[15][2] = 16;

HEU.qr[16][1] = 12;

For example, HEU.qr[16][1] = 12 means that node 16 has only one neighbor and is 12. So, HEU.qr[15][1] = 14 and HEU.qr[15][2] = 16 means that node 15 has two neighbors that are 14 and 16.

The auxiliary functions are those:

int vazio(GRAPHD &HEU) {
for (int i = 1; i <= HEU.nb_nodes; i++) {
    if (HEU.Q[i] != 0)
        return 0;
}
return 1;
}

int extract_mimimum(GRAPHD &HEU) {
int min = INT_MAX;
for (int i = 1; i <= HEU.nb_nodes; i++) {
    if (HEU.Q[i] != 0) {
        if (HEU.d[i] < min) {
            min = i;                
        }
    }
}
return min;
}

void retira(GRAPHD &HEU, int a) {
for (int i = 1; i <= HEU.nb_nodes; i++) {
    if (HEU.Q[i] == a) HEU.Q[i] = 0;
}
 }

The vector of distances starting at node 2 should be 1 0 1 2 3 2 3 3 4 3 6 6 5 4 5 but is being 1 0 1 2 3 2 3 3 4 8 7 6 7. Could someone help me?