Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
FreeMan108
121 / 121 / 32
Регистрация: 04.03.2013
Сообщений: 370
#1

Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом - C++

15.11.2014, 16:40. Просмотров 612. Ответов 6
Метки нет (Все метки)

Здравствуйте! Пишут, что можно находить кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом. Как такое вообще возможно, ведь можно как угодно долго ходить по одному ребру с отрицательным весом, тем самым уменьшая целевой путь?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2014, 16:40
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом (C++):

Найти минимальное расстояние между вершинами 1 и N графа
Dev-C++ не компилирует программу Решил написать алгоритм 0,1-BFS void...

Алгоритм для поиска всех путей между 2 вершинами графа
Здравствуйте, возник вопрос какой алгоритм необходимо использовать для поиска...

Найти максимальное и среднее расстояние между центральными вершинами неориентированного графа
Здравствуйте. нужно найти максимальное и среднее расстояние между центральными...

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

Написать программу для нахождения кратчайшего пути между заданными вершинами графа
visual studio windows forms нужна программа,которая будет вычислять...

Поиск самых коротких расстояний между любыми двумя вершинами графа по методу Шимбела
у меня большие проблемы с логикой программирования) поэтому обращаюсь к вам за...

6
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
15.11.2014, 16:44 #2
Цитата Сообщение от FreeMan108 Посмотреть сообщение
Здравствуйте! Пишут, что можно находить кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом. Как такое вообще возможно, ведь можно как угодно долго ходить по одному ребру с отрицательным весом, тем самым уменьшая целевой путь?
а вот никак
где такое пишут?
0
FreeMan108
121 / 121 / 32
Регистрация: 04.03.2013
Сообщений: 370
15.11.2014, 16:53  [ТС] #3
Цитата Сообщение от Dani Посмотреть сообщение
где такое пишут?
Сразу первая строчка
https://ru.wikipedia.org/wiki/%D0%90...B8%D1%82%D0%B0
0
Renji
2141 / 1500 / 456
Регистрация: 05.06.2014
Сообщений: 4,338
15.11.2014, 17:00 #4
Видимо, фокус в том, что граф ориентированный.
0
FreeMan108
121 / 121 / 32
Регистрация: 04.03.2013
Сообщений: 370
15.11.2014, 17:05  [ТС] #5
Цитата Сообщение от Renji Посмотреть сообщение
Видимо, фокус в том, что граф ориентированный.
Если связь между двумя вершинами ориентированная, то это дуга, а не ребро, по определению.
0
Renji
2141 / 1500 / 456
Регистрация: 05.06.2014
Сообщений: 4,338
15.11.2014, 17:08 #6
Цитата Сообщение от FreeMan108 Посмотреть сообщение
Если связь между двумя вершинами ориентированная, то это дуга, а не ребро, по определению.
Значит читаем ВП:ОТКАЗ и больше не полагаемся на материалы из Википедии.
0
FreeMan108
121 / 121 / 32
Регистрация: 04.03.2013
Сообщений: 370
15.11.2014, 17:15  [ТС] #7
Так это не только в вики. Вот еще
http://comp-science.narod.ru/KPG/Index.htm

Добавлено через 1 минуту
Или это они друг у друга дезу передирают?
0
15.11.2014, 17:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2014, 17:15
Привет! Вот еще темы с решениями:

Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину
В неориентированном графе требуется найти минимальный путь между двумя...

Напечатать таблицу соответствия между весом в фунтах и весом в килограммах
Напечатать таблицу соответствия между весом в фунтах и весом в килограммах для...

Циклы for: таблица соответствия между весом в фунтах и весом в килограммах
//1. Напечатать таблицу соответствия между весом в фунтах и весом в килограммах...

Графы: найти путь между вершинами, имеющий наименьшую суммарную протяженность аварийно-опасных участков
Имеется сеть автомобильных дорог. Известны расстояния всех участков дорог....


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

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

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