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

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

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

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

19.07.2016, 09:17. Просмотров 285. Ответов 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 секунду
просто не понимаю тему
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.07.2016, 09:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Посчитать длины кратчайших путей ориентированного графа (C++):

Поиск кратчайших путей из одного источника для неориентированного графа - C++
Дорогие программисты! Прошу вас помочь мне в очень срочном деле! Очень нужен код программы, которая в заголовке на С++. Нашла целую...

Нахождения кратчайших путей между всеми парами вершин графа - C++
Подскажите как можно улучшить алгоритм Флойда-Уоршелла что-бы он верно работал если длина некоторых векторов равно 0 (то есть отсутствую). ...

Поиск кратчайших путей между двумя вершинами графа методом Шимбела. - C++
Доброго всем время суток!! В универе задали на РГР написать программу в С++, которая находит кратчайший путь между двумя вершинами графа,...

Поиск кратчайших путей в графе - C++
Владислав Исенбаев — двукратный чемпион Урала по программированию, вице-чемпион TopCoder Open 2009, абсолютный чемпион ACM ICPC 2009. За то...

Прогрмма по поиску кратчайших путей в графе - C++
Всю голову поломал,но вот что-то толком не получается(((Нужна программа по поиску кратчайших путей в графе на основе теории нечетких...

Дан ориентированный граф, нужно на выходе получить матрицу кратчайших путей - C++
Добрый день,задача состоит в следующем: Дан ориентированный граф(матрица смежности с бесконечностями),задана правильная нумерация.Нужно на...

3
senich
61 / 61 / 23
Регистрация: 22.11.2012
Сообщений: 241
Записей в блоге: 1
19.07.2016, 09:46 #2
Смотрите на вторую строку своего условия, видите "алгоритм Форда-Беллмана", ищете его в гугле, находите сайт [на указанном сайте обнаружено вредоносное содержимое, ссылка удалена], читаете объяснение этого алгоритма, копируете готовый код оттуда, добавляете ввод и вывод.
0
game1progg
31 / 1 / 0
Регистрация: 07.01.2016
Сообщений: 44
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 может сам сделаешь ввод и вывод?
0
senich
61 / 61 / 23
Регистрация: 22.11.2012
Сообщений: 241
Записей в блоге: 1
21.07.2016, 10:19 #4
game1progg Вау, вы умеете копировать код!
Нет, не буду ничего делать, потому что вы сами и строчки кода написать не можете.
0
21.07.2016, 10:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.07.2016, 10:19
Привет! Вот еще темы с ответами:

Построение ориентированного графа - C++
Привет!) Покажу код, то что я делал. На выходе нету расстояний(стоимости). Как добавить расстояние на графе. #include...

Найти квадрат ориентированного графа - C++
Здравствуйте , помогите, пожалуйста решить задачу по графам: 1.Дан ориентированный граф. Найти квадрат ориентированного графа

Матрица/связные_списки смежности для ориентированного графа - C++
Скажите, пожалуйста, когда я создаю матрицу смежности для ориентированного графа, то в матрице у меня должны присутствовать только 0 и 1?...

Алгоритмы поиска кратчайших путей в ширину и двунаправленный в ширину - C++
Реализовать алгоритм поиска кратчайшего пути. Двунаправленный поиск в ширину. Вот есть 2 алгоритма поиска в ширину. ...


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

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

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