Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
game1progg
31 / 1 / 0
Регистрация: 07.01.2016
Сообщений: 41
#1

Посчитать длины кратчайших путей ориентированного графа - C++

19.07.2016, 09:17. Просмотров 247. Ответов 3
Метки нет (Все метки)

есть задача :
задача №138
Алгоритм Форда-Беллмана
(Время: 1 сек. Память: 16 Мб Сложность: 38%)
Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

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

Входные данные

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

Выходные данные

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

Добавлено через 1 минуту
мне нужен простенький код, без map-ов и чего в этом роде, вопрос открыт пока я не напишу

Добавлено через 41 секунду
просто не понимаю тему
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.07.2016, 09:17     Посчитать длины кратчайших путей ориентированного графа
Посмотрите здесь:
Нахождения кратчайших путей между всеми парами вершин графа C++
C++ Поиск кратчайших путей из одного источника для неориентированного графа
C++ Поиск кратчайших путей между двумя вершинами графа методом Шимбела.
C++ Поиск кратчайших путей в графе
C++ Прогрмма по поиску кратчайших путей в графе
Дан ориентированный граф, нужно на выходе получить матрицу кратчайших путей C++
Построение ориентированного графа C++
C++ Матрица/связные_списки смежности для ориентированного графа
C++ Алгоритмы поиска кратчайших путей в ширину и двунаправленный в ширину
C++ Составить программу печати всех циклов ориентированного графа
C++ Найти диаметр графа, то есть, максимальное значение среди всех кратчайших расстояний между каждой парой вершин
Поиск самого длинного пути от первой до последней вершины ацикличного ориентированного невзвешенного графа C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
senich
61 / 61 / 23
Регистрация: 22.11.2012
Сообщений: 242
Записей в блоге: 1
19.07.2016, 09:46     Посчитать длины кратчайших путей ориентированного графа #2
Смотрите на вторую строку своего условия, видите "алгоритм Форда-Беллмана", ищете его в гугле, находите сайт [на указанном сайте обнаружено вредоносное содержимое, ссылка удалена], читаете объяснение этого алгоритма, копируете готовый код оттуда, добавляете ввод и вывод.
game1progg
31 / 1 / 0
Регистрация: 07.01.2016
Сообщений: 41
21.07.2016, 08:02  [ТС]     Посчитать длины кратчайших путей ориентированного графа #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct edge {
    int a, b, cost;
};
 
int n, m, v;
vector<edge> e;
const int INF = 1000000000;
 
void solve() {
    vector<int> d (n, INF);
    d[v] = 0;
    for (int i=0; i<n-1; ++i)
        for (int j=0; j<m; ++j)
            if (d[e[j].a] < INF)
                d[e[j].b] = min (d[e[j].b], d[e[j].a] + e[j].cost);
    // вывод d, например, на экран
}
senich может сам сделаешь ввод и вывод?
senich
61 / 61 / 23
Регистрация: 22.11.2012
Сообщений: 242
Записей в блоге: 1
21.07.2016, 10:19     Посчитать длины кратчайших путей ориентированного графа #4
game1progg Вау, вы умеете копировать код!
Нет, не буду ничего делать, потому что вы сами и строчки кода написать не можете.
Yandex
Объявления
21.07.2016, 10:19     Посчитать длины кратчайших путей ориентированного графа
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru