Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.68/34: Рейтинг темы: голосов - 34, средняя оценка - 4.68
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943

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

31.08.2018, 17:06. Показов 7275. Ответов 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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
31.08.2018, 17:06
Ответы с готовыми решениями:

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

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

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

5
31.08.2018, 17:35

Не по теме:

del

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

Решение

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

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

Решение

Если этой проверки не будет, то при наличии в графе отрицательных весов, можно получить посещение вершины, в которую невозможно попасть из начальной вершины 1. Например, в графе нет путей из 1 в вершины 10 и 11, но есть ребро 10->11 с весом -10. Тогда без добавленной проверки вершине 11 будет присвоено значение 30000-10=29990, т.е. что в неё есть путь.
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
31.08.2018, 21:39
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru