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

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

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

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

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

Требуется посчитать длины кратчайших путей от вершины номер 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
Ответ Создать тему
Опции темы

Новые блоги и статьи
Kanban или Scrum - что выбрать?
EggHead 27.04.2025
Kanban и Scrum — уже много лет удерживают лидирующие позиции среди гибких подходов. Руководители проектов и команды разработчиков то и дело сталкиваются с дилеммой: какой из этих двух методов выбрать. . .
Кастомные Middleware на C# в ASP.NET Core
UnmanagedCoder 27.04.2025
Разработка веб-приложений сегодня мало напоминает монолитное программирование прошлых лет. На смену громоздким блокам кода пришла модульная архитектура, где каждый компонент выполняет строго. . .
Анализ и линтинг кода JavaScript: ESLint, Prettier и JSHint
run.dev 26.04.2025
JavaScript прошёл долгий путь от простого языка для анимации веб-страниц до основы современной веб-разработки. С ростом сложности приложений, увеличением кодовых баз и масштабированием команд. . .
Паттерны в Python: Singleton, Factory и Observer
py-thonny 26.04.2025
Паттерны проектирования — это проверенные временем решения типовых проблем разработки программного обеспечения. Их история берёт начало с книги "Приёмы объектно-ориентированного проектирования. . . .
Исключения в C#: Stack Overflow, Access Violation и Out of memory
stackOverflow 26.04.2025
Исключения в C# — это не только механизм оповещения о проблемах, а целое искусство управления потоком выполнения программы в экстремальных ситуациях. Обычное исключение, например,. . .
Логирование в C# ASP.NET Core с помощью Serilog, ElasticSearch, Kibana
stackOverflow 25.04.2025
Помните те времена, когда для анализа проблемы приходилось подключаться к серверу, искать нужный лог-файл среди десятков других и вручную фильтровать тысячи строк в поисках ошибки? К счастью, эти дни. . .
Структура "железный OnKeyUp" вместо антидребезга. Полностью асинхронный счётчик.
Hrethgir 25.04.2025
Программа для симуляции схемы - Logisim Evolution В общем какое-то время отвлёкся, так было надо, теперь когда запилю это на verilog и FPGA , досоставлю заявку в ФИПС на полезную модель - не готов. . .
Автоматизация Amazon Web Services (AWS) с Boto3 в Python
py-thonny 25.04.2025
Облачные вычисления стали неотъемлемой частью современной ИТ-инфраструктуры, а Amazon Web Services (AWS) занимает лидирующие позиции среди провайдеров облачных услуг. Управление многочисленными. . .
Apache Kafka vs RabbitMQ в микросервисной архитектуре
ArchitectMsa 25.04.2025
Современная разработка ПО всё чаще склоняется к микросервисной архитектуре — подходу, при котором приложение разбивается на множество небольших, автономных сервисов. В этой распределённой среде. . .
Параллельное программирование с OpenMP в C++
NullReferenced 24.04.2025
Параллельное программирование — подход к созданию программ, когда одна задача разбивается на несколько подзадач, которые могут выполняться одновременно. Оно стало необходимым навыком для. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru