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

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

Войти
Регистрация
Восстановить пароль
 
God_Krom
1 / 1 / 0
Регистрация: 03.05.2011
Сообщений: 19
#1

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

03.05.2011, 20:49. Просмотров 981. Ответов 4
Метки нет (Все метки)

Помоги,будьте любезный.Всех прошу.Не могу написать сам алгоритм нахождения этого наибольшего пути.матрица смежности храниться в текстовом файле.буду очень рад если поможете.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2011, 20:49     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней
Посмотрите здесь:

Нахождение кратчайшего пути от одной вершины графа до другой C++
Найти отрезок максимальной длины в массиве А C++
C++ Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
C++ нахождение Максимальной длины имени объекта Fat32
C++ Слово максимальной длины заменить на слово минимальной длины
C++ Графы,исключение из пути определённых вершины
Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. C++
Вывод двух слов максимальной длины C++
Поиск самого длинного пути от первой до последней вершины ацикличного ориентированного невзвешенного графа C++
C++ Подсветить предложение максимальной длины
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А C++
В файле заменить все слова максимальной длины на слова минимальной длины C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Veyron
 Аватар для Veyron
105 / 105 / 4
Регистрация: 02.06.2009
Сообщений: 579
03.05.2011, 22:56     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней #2
Задача решается обходом в ширину, так как граф обязательно будет деревом.
God_Krom
1 / 1 / 0
Регистрация: 03.05.2011
Сообщений: 19
04.05.2011, 00:34  [ТС]     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней #3
Если Тебе не тяжело,Ты бы не мог написать код этого обхода.
Veyron
 Аватар для Veyron
105 / 105 / 4
Регистрация: 02.06.2009
Сообщений: 579
04.05.2011, 08:14     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней #4
Обход в ширину

Это основной обход. Для решения задачи необходимо его расширить.
Массив посещений можно не сохрянять, потому что граф является ацикличным и мы не зациклимся на какой-то вершине, а иначе задача не решается (можно мотать бесконечно большой путь). Создадим массив расстояния от первой до текущей вершины. Сначала инициализируем все ячейки -1, а в первую пишем 0. Запускаем обход.
При обходе из всех выходящих из текущей вершин нужно прибавить по единице. При этом смотреть, нет ли там чего-то. Если есть, то сравнить значение, которое хотим присвоить и значение, которое уже есть там. Выбрать из них максимум и присвоить ячейке. В конце просто нужно вывести содержимое этого массива в последней ячейке.
God_Krom
1 / 1 / 0
Регистрация: 03.05.2011
Сообщений: 19
04.05.2011, 19:42  [ТС]     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней #5
Спасибо большое.Буду пробовать.
Yandex
Объявления
04.05.2011, 19:42     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней
Ответ Создать тему
Опции темы

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