Что за ошибка во время вывода?

Question

[impelix]

Начал пытаться выводить предков после алгоритма дейкстры. И получаю такой вывод.

вывод

3
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

Сам код

код

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;
//int g[20000][2000], used[20000], dist[20000];
vector<int> dist;
vector<bool> used;
vector <int> p;
void relax(int i, int j, int h){
    if (dist[i] + h < dist[j]) {
        dist[j] = dist[i] + h;
        p[j] = i;
    }
    }


int main() {
    int n, s, f, v, min;
    cin >> n >> s >> f;
    --s;
    //--f;
    int g[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }
    used.resize(n, 0);
    dist.resize(n, INT_MAX);
    p.resize(n);
    dist[s] = 0;
    for(int i = 0; i < n; i++) {
        min = INT_MAX;
        v = -1;
        for (int j = 0; j < n; j++) {
            if (used[j] == 0 && dist[j] < min) {
                min = dist[j];
                v = j;
            }
        }
            if (v < 0) break;
        for (int j = 0; j < n; j++)
            if (used[j] == 0 && g[v][j] != -1) {
                relax(v, j, g[v][j]);
                p[j] = v;
            }
            used[v] = 1;
        }

    if (dist[f] == INT_MAX) {
        cout << "-1";
        return 0;
    }
    cout << dist[--f] << endl;
    vector<int> path;
    for (int v = f; v != s; v = p[v])
        path.push_back(v);
    path.push_back (s);
    reverse(path.begin(), path.end());
    for(auto elem : path)
        cout << elem  << ' ';
}

Answer 1

[Wataru]

Блин, вы что, случайно код пишите, пока он не заработает? Можете вниматиельно прочитать свой код и объяснить себе, зачем там каждая строчка нужна? Прогнать его в дебаггере или в голове - строчка за строчкой, записывая значения переменных в тетрадке?

У вас опять куча мелких ошибок в коде.

На вскидку:
f надо уменьшать там, где у вас закомментированно, после ввода. А то вы после основного цикла обращаетесь по индексу не уменьшенного f и выходите за границу массива.

Массив p надо переписывать только при удачной релаксации, вы же в основном цикле, после вызова функции еще зачем-то всегда переписываете предка. Из-за этого у вас там полный бред в массиве ссылок к предку получается и цикл вывода, скорее всего, виснет в бесконечном цикле из ссылок.

Comments

[impelix]

Начнем по порядку. То что --f закомментирован роли не играло, насчет сохранения предка он сохраняется только после удачно релаксации, об этом говорит как минимум правильный вывод программы(части которая считает). Присваиваю я предка только после релаксации вершины. Потом начинаю идти от вершины f и добавляю каждого предка в вектор, пока f != s. f постоянно обновляется и вроде как когда то придет к s. Опять сам алгоритм Дейкстра написан правильно, так как вес верный выводит, проверенно.
В подтверждении кусок кода

if (used[j] == 0 && g[v][j] != -1) {
                relax(v, j, g[v][j]);
                p[j] = v;
            }

Где предок присваивается только после релаксации, и по итогу остается только собрать предков, вот собственно где и возникает проблема.

for (int v = f; v != s; v = p[v]) {
        path.push_back(v);
    }
    path.push_back (s);
    reverse(path.begin(), path.end());
    for (auto elem: path)
    {
        cout << elem << ' ';
    }

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

[Wataru]

impelix, Почему вы присваиваете предка для j на v? А если там расстояние уже записано было лучше?

Присваивание p не влияет на рассчеты расстояния, поэтому вывод расстояния будет правильным, даже если p рассчитано вообще неверно.

Ошибки в коде восстановления пути нет. Ошибка в коде рассчета предков.