@impelix

Как исправить алгоритм Дейкстры?

Написал алгоритм дейкстры, но он не работает. Про время знаю что не самый быстрый, но это пока не важно.
Входные данные: размер и сама матрица смежности и точка старта и точка до которой надо вывести расстояние от точки старта. Сам алгоритм ниже.
Не пойму почему выводит инт макс, пробовал отдебажить не получилось
Код
#include <iostream>
#include <vector>
#include <climits>

using namespace std;
//int g[20000][2000], used[20000], dist[20000];
vector<int> dist(6, INT_MAX);
vector<bool> used(6);

void relax(int i, int j, int h){
    if (dist[i] + h < dist[j])
        dist[j] = dist[i] + h;
    }

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

Пример
Ввод:
3 2 1
0 1 1
4 0 1
2 1 0
Вывод:
3
Также надо сделать восстановление пути, но благодаря бфсу я уже этому научился :)
  • Вопрос задан
  • 181 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Раз уж я в комментариях все разобрал, скопирую в ответ: куча мелких ошибок в коде, вроде:
- циклы с 1 вместо 0
- не инициализированные массивы
- опечатки
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы