Алгоритм Дейкстры

#cpp #алгоритм

Мне нужно восстановить минимальный путь в графе, от вершины s до f, используя алгоритм
Дейкстры. Моя идея - запоминать вершину-родителя для каждой вершины, относительно минимального
расстояния для которой мы уверены. Решение не проходит половину тестов, не могли вы
помочь мне, указав на ошибку?

#include 
#include 
#include 
#include 
#include 

using namespace std;

vector > graph;
vector dist;
vector used;
vector parrent;

void djkstera(long long u, long long &n, long long &v){
    set > que;
    que.insert({0, u});
    dist[u] = 0;
    long long parr = u;

    while(!que.empty()){

        while(!que.empty() && used[(*que.begin()).second]){
            que.erase(que.begin());
        }

        if(que.empty())
            break;

        u = (*que.begin()).second;
        used[u] = true;
        parrent[u] = parr;
        parr = u;
        que.erase(que.begin());

        for(long long i = 0; i < n; ++i){
            if(graph[u][i] != -1 and u!=i){
                dist[i] = min(dist[i], dist[u] + graph[u][i]);
                que.insert({dist[i], i});
            }
        }
    }
}

int main() {
    long long n,s,f;
    cin >> n >> s >> f; // s - start, f - finish
    s--; f--;
    graph.assign(n, vector(n));
    used.assign(n, false);
    dist.assign(n, INT64_MAX);
    parrent.resize(n);

    //Граф задаётся матрицой смежности
    for(long long i = 0; i < n; ++i){
        for(long long j = 0; j < n; ++j){
            cin >> graph[i][j];
        }
    }
    djkstera(s, n, f);

    //Пути не существует
    if(dist[f] == INT64_MAX){
        cout << "No solution";
        return 0;
    }

    vector res;
    for(long long i = f; i != s; i = parrent[i]){
         res.push_back(i + 1);
    }
    res.push_back(s + 1);
    reverse(res.begin(), res.end());

    copy(res.begin(), res.end(), ostream_iterator(cout, " "));

    return 0;
}

    

Ответы

Ответ 1

Всё, сам разобрался.
Родителя следует определять после удачной релаксации(если значение в массиве dist
было изменено). Получается вот так:

for(long long i = 0; i < n; ++i){
    if(graph[u][i] != -1 and u!=i){
        if(dist[u] + graph[u][i] < dist[i]){
            parrent[i] = u;
            dist[i] = dist[u] + graph[u][i];
        }
        que.insert({dist[i], i});
    }
}