192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 942
1

Алгоритм Беллмана-Форда

31.08.2018, 17:06. Показов 6218. Ответов 5
Метки нет (Все метки)

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

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

Входные данные
В первой строке входного файла INPUT.TXT записаны целые числа N и M - количество вершин и количество ребер графа (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000). В каждой из последующих M строк записана тройка чисел, описывающих ребра: начало ребра, конец ребра и вес (вес - целое число от -100 до 100).

Выходные данные
В выходной файл OUTPUT.TXT выведите N чисел - расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

input.txt
4 5
1 2 10
2 3 10
1 3 100
3 1 -10
2 3 1

output.txt
0 10 11 30000


мой код первый тест проходит а второй нет. Подозреваю что что то не так понимаю насчёт петли или кратных ребер
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <cstdlib>
#include <list>
#include <vector>
 
const int SIZE = 102;
 
void bellman_ford(
    std::list<int> (&a)[SIZE],
    const int n,
    std::vector<int> &shortest
) {
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j <= n; ++j) {
            for(std::list<int>::iterator it = a[j].begin(); it != a[j].end();) {
                int v = *it++;
                int w = *it++;
                if(shortest[j] + w < shortest[v]) {
                    shortest[v] = shortest[j] + w;
                }
            }
        }
    }
}
 
int main() {
    freopen("c:\\input.txt", "rt", stdin);
    freopen("c:\\output.txt", "wt", stdout);
    std::list<int> a[SIZE];
    int n, m, s;
    int u, v, w;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        if(u == v) {      // петлю не рассматриваю
            continue;
        }
        a[u].push_back(v);
        a[u].push_back(w);
    }
    s = 1;
    std::vector<int> shortest(n + 1, 30000);
    shortest[s] = 0;
    bellman_ford(a, n, shortest);
    for(int i = 1; i <= n; ++i) {
        printf("%d ", shortest[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.08.2018, 17:06
Ответы с готовыми решениями:

Алгоритм Форда-Беллмана
Доброго времени суток. Есть кривой код: #include &lt;iostream&gt; #include &lt;vector&gt; using namespace...

Алгоритм Форда-Беллмана
Народ если есть у кого нибудь исходник выложите пожалуйста очень надо. А то везде одно и то же......

Алгоритм Форда - Беллмана
Помогите пожалуйста понять что не так у меня. ограничение времени на тест: 1 сек. ограничение...

Матрица Форда Беллмана и метод Дейкстра
Тут такая проблема , задали написать матрицу с помощью єтих методов/ вопрос : Как вставить сюда...

5
Mournful Max
31.08.2018, 17:35
  #2

Не по теме:

del

1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 942
31.08.2018, 17:41  [ТС] 3
Цитата Сообщение от Captain Maxee Посмотреть сообщение
Тут точно нет выхода за пределы при j == n
Спасибо что ответили, выхода нет и не может быть потому что максимальное кол-во вершин может быть равна 100 а у меня список размера SIZE который равен 102
1
165 / 114 / 59
Регистрация: 12.07.2018
Сообщений: 277
31.08.2018, 20:27 4
Лучший ответ Сообщение было отмечено no swear как решение

Решение

no swear, после строки 17 должна быть проверка на то, что мы посещали эту вершину:

C++
1
if(shortest[j] < 30000)
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 942
31.08.2018, 21:00  [ТС] 5
Спасибо большое, все тесты прошло, но я не до конца понимаю зачем нужна эта проверка? Значит я не понял суть этого алгоритма?
Можете объяснить пожалуйста что эта проверка даёт?
0
165 / 114 / 59
Регистрация: 12.07.2018
Сообщений: 277
31.08.2018, 21:39 6
Лучший ответ Сообщение было отмечено no swear как решение

Решение

Если этой проверки не будет, то при наличии в графе отрицательных весов, можно получить посещение вершины, в которую невозможно попасть из начальной вершины 1. Например, в графе нет путей из 1 в вершины 10 и 11, но есть ребро 10->11 с весом -10. Тогда без добавленной проверки вершине 11 будет присвоено значение 30000-10=29990, т.е. что в неё есть путь.
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.08.2018, 21:39
Помогаю со студенческими работами здесь

Графы: реализация алгоритма Беллмана-Форда
Написать программу, реализующую алгоритм Беллмана-Форда.

Восстановление пути из алгоритма Форда-Беллмана
Реализовал алгоритм Форда-Беллмана, но не получается правильно восстановить пути, подскажите, где...

Алгоритм Форда
Здравствуйте, помогите пожалуйста с задачей. Дан граф. Каждой дуге приписано некоторое число...

Алгоритм Форда-Белмана
Найти расстояние от фиксированной вершины до всех остальных вершин графа. Для задания любая матрица...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru