I'm implementing the dijkstra algorithm to find the smallest path on a network. Starting from a source node s, I need to calculate the smallest path to reach all the other nodes that exist on the network. But the algorithm is not working properly.
Here is 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 from node 2. All distances in the array HEU.c [] [] are 1 and the graph is 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 these:
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 distance vector starting at node 2 should be 1 0 1 2 2 3 2 3 3 4 3 6 6 5 4 5 but it is 1 0 1 2 2 3 2 3 3 4 3 8 8 7 6 7. Could someone help me?