Задачи по поиску кратчайшего пути с помощью Дейкстры - PullRequest
Новая
       12

Задачи по поиску кратчайшего пути с помощью Дейкстры

0 голосов
/ 01 ноября 2018

Я реализую алгоритм Dijjkstra, чтобы найти кратчайший путь в сети. Начиная с исходного узла s, мне нужно рассчитать кратчайший путь для достижения всех существующих узлов в сети. Но алгоритм не делает это правильно.

Вот код (HEU - это структура Графа): 

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) { //it's just to indicate that the position is not empty
            if (HEU.qr[u][i] != -2) { //it's just to indicate that the position is not empty
                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;
}

Проблема при запуске с узла 2. Все расстояния в матрице HEU.c [] [] равны 1, а график выглядит следующим образом: 

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;

Например, HEU.qr [16] [1] = 12 означает, что узел 16 имеет только одного соседа и его узел 12. Тогда HEU.qr [15] [1] = 14 и HEU.qr [15] [2] = 16 узел 15 имеет двух соседей: 14 и 16.

Вспомогательные функции: 

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

Вектор расстояния, начинающийся с узла 2, должен быть 1 0 1 2 2 3 2 3 3 4 3 6 6 5 4 5, но алгоритм находит 1 0 1 2 2 3 2 3 3 4 3 8 8 7 6 7. Может кто-нибудь, пожалуйста, помогите мне?

...