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

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

Войти
Регистрация
Восстановить пароль
 
FreeMan108
121 / 121 / 6
Регистрация: 04.03.2013
Сообщений: 370
#1

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

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

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

Найти минимальное расстояние между вершинами 1 и N графа - C++
Dev-C++ не компилирует программу Решил написать алгоритм 0,1-BFS void BFS(int** MasList, int** MasListW, int& N,int& S){ int*...

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

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

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

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

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

6
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,290
Записей в блоге: 2
Завершенные тесты: 1
15.11.2014, 16:44 #2
Цитата Сообщение от FreeMan108 Посмотреть сообщение
Здравствуйте! Пишут, что можно находить кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом. Как такое вообще возможно, ведь можно как угодно долго ходить по одному ребру с отрицательным весом, тем самым уменьшая целевой путь?
а вот никак
где такое пишут?
0
FreeMan108
121 / 121 / 6
Регистрация: 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
1999 / 1367 / 308
Регистрация: 05.06.2014
Сообщений: 3,899
15.11.2014, 17:00 #4
Видимо, фокус в том, что граф ориентированный.
0
FreeMan108
121 / 121 / 6
Регистрация: 04.03.2013
Сообщений: 370
15.11.2014, 17:05  [ТС] #5
Цитата Сообщение от Renji Посмотреть сообщение
Видимо, фокус в том, что граф ориентированный.
Если связь между двумя вершинами ориентированная, то это дуга, а не ребро, по определению.
0
Renji
1999 / 1367 / 308
Регистрация: 05.06.2014
Сообщений: 3,899
15.11.2014, 17:08 #6
Цитата Сообщение от FreeMan108 Посмотреть сообщение
Если связь между двумя вершинами ориентированная, то это дуга, а не ребро, по определению.
Значит читаем ВП:ОТКАЗ и больше не полагаемся на материалы из Википедии.
0
FreeMan108
121 / 121 / 6
Регистрация: 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
Привет! Вот еще темы с ответами:

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

Циклы for: таблица соответствия между весом в фунтах и весом в килограммах - C++
//1. Напечатать таблицу соответствия между весом в фунтах и весом в килограммах для значений 1, 2, ..., 10 фунтов(1 фунт = 453 г). ...

Напечатать таблицу соответствия между весом в фунтах и весом в килограммах - C++
Напечатать таблицу соответствия между весом в фунтах и весом в килограммах для значений 1, 2, ... ,10 фунтов(1 фунт=453г)

Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами - C++
Ребята день добрый. Задание у меня вот такое: Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между...


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

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

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