|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.10.2017, 20:48 | #1 |
Новичок
Джуниор
Регистрация: 09.10.2017
Сообщений: 1
|
Найти самый длинный путь из вершины Х в У
Помогите разобраться с заданием! Поиск самого короткого пути не составляет проблем, а вот самого длинного... даже нет никаких идей, как это сделать.
Задание: Постройте матрицу смежности для описания графа. Найти самый длинный путь между вершинами Х и У. Номера вершин вводит пользователь. Граф, для которого нужно реализовать, во вложении. Заранее спасибо за помощь!!! |
09.10.2017, 21:05 | #2 |
Участник клуба
Регистрация: 14.05.2016
Сообщений: 1,793
|
Я не в курсу, но могу предположить, что надо будет поменять "<" на ">" (т.е. искать не меньше, а больше) и всё.
Другими словами, возьми любой метод поиска минимального пути (например Дейкстры - ведь у тебя проблем нет в его реализации): https://www.youtube.com/watch?v=UA6aV1XJCGg и замени "мин" на "макс" (в 8:19мин он что-то такое говорит). |
09.10.2017, 21:17 | #3 | |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
Цитата:
При поиске самого короткого пути мы перебираем все рёбра с началом в текущей вершине и каждый раз проверяем, не будет ли путь до текущей вершины плюс длина ребра короче ранее найденного пути в конец ребра. А теперь нужно только поменять условие и проверять, не будет ли сумма длиннее. Только если в графе будут циклы, алгоритм пойдёт по кругу |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Самый длинный (максимальный) путь в графе - Java SE | AlexMin | Помощь студентам | 7 | 16.01.2017 20:45 |
самый дешевый путь | Евгений1415 | Помощь студентам | 13 | 31.01.2016 11:43 |
путь от одной вершины графа к другой | Катя Горбачева | Помощь студентам | 5 | 14.04.2011 20:05 |
найти вершины квадрата | dimon131 | Общие вопросы C/C++ | 7 | 23.12.2010 12:04 |
Самый дешевый путь. Графы. | jocry | Помощь студентам | 1 | 14.03.2009 12:56 |