Найти самый длинный путь из вершины Х в У

[Noob666]

Помогите разобраться с заданием! Поиск самого короткого пути не составляет проблем, а вот самого длинного... даже нет никаких идей, как это сделать.

Задание:
Постройте матрицу смежности для описания графа. Найти самый длинный путь между вершинами Х и У. Номера вершин вводит пользователь.

Граф, для которого нужно реализовать, во вложении.
Заранее спасибо за помощь!!!

[ura_111]

Я не в курсу, но могу предположить, что надо будет поменять "<" на ">" (т.е. искать не меньше, а больше) и всё.

Другими словами, возьми любой метод поиска минимального пути (например Дейкстры - ведь у тебя проблем нет в его реализации):

https://www.youtube.com/watch?v=UA6aV1XJCGg

и замени "мин" на "макс" (в 8:19мин он что-то такое говорит).

[Black Fregat]

Сообщение от Noob666

Поиск самого короткого пути не составляет проблем, а вот самого длинного... даже нет никаких идей, как это сделать.

В чём, собственно проблема?

При поиске самого короткого пути мы перебираем все рёбра с началом в текущей вершине и каждый раз проверяем, не будет ли путь до текущей вершины плюс длина ребра короче ранее найденного пути в конец ребра.

А теперь нужно только поменять условие и проверять, не будет ли сумма длиннее.

Только если в графе будут циклы, алгоритм пойдёт по кругу