4

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <iterator>

using namespace std;

vector<vector<long long> > graph;
vector<long long> dist;
vector<long long> used;
vector<long long> parrent;

void djkstera(long long u, long long &n, long long &v){
    set<pair<long long, long long> > 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<long long>(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<long long> 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<long long>(cout, " "));

    return 0;
}
1
  • А в чем глубинный смысл выборочной передачи параметров по ссылке? 7 июл 2018 в 14:24

1 ответ 1

2

Всё, сам разобрался. Родителя следует определять после удачной релаксации(если значение в массиве 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});
    }
}
4
  • Из-за того, что вы всегда вставляете пару в que вам приходится устраивать всю эту возню с массивом used и циклом удаления в начале. Может разумнее было бы просто удалять старое значение из очереди и вставлять новое? Тогда массив used и связанный с ним цикл не понадобился бы вообще. 7 июл 2018 в 14:42
  • @AnT Контейнер que нужен для выбора вершины, относительно минимального расстояния для которой мы уверены. Пусть мы начинаем поиск кратчайшего пути с вершины v. Из неё имеются рёбра в некоторое множество вершин U. Пусть u ∈ U, и вес ребра из v в u меньше, нежели для остальных элементов множества U. Тогда я утверждаю, что вес этого ребра - и есть минимально возможное расстояние из вершины v в u(доказывать, думаю, не надо). Для выбора такого ребра мы можем пройтись по всем рёбрам за O(N), с помощью set я делаю это за O(log(n)). 8 июл 2018 в 7:50
  • Это прекрасно. Но у вас одна и та же вершина попадает в que много раз: при каждом изменении значения расстояния. Именно из-за этого вам приходится заводить еще и массив used - чтобы одну и ту же вершину много раз не обрабатывать. А вот если бы вы позаботились о том, что каждая вершина присутствует в que гарантированно не более одного раза, то тогда ни used, ни вся возня с ним не понадобилась бы. 8 июл 2018 в 8:08
  • @AnT Это тоже прекрасно, но тогда не могли вы предложить идею реализации этого? Я не могу придумать, как избавиться от массива used в случае, например, цикличного графа. На сколько я знаю, все алгоритмы, которые основаны на обходе графа используют массив подобного назначения. 8 июл 2018 в 8:43

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.