| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск путей в графе |
| Автор: gabiturat 27.4.2016, 19:48 |
| Подскажите, кто разбирается в теме. Имеется взвешенный ориентированный граф без циклов. Нужно найти в нем путь наибольшей длины, у которого вес удовлетворяет заданному ограничению. Если таких путей много, то желательно найти все, но можно хотя бы первый попавшийся. Первое что приходит на ум: найти все пути среди всех пар вершин, выбрать те, у которых вес подходит, и среди них уже выбрать самые длинные. Это единственный способ, или возможны какие-то более оптимальные решения? |
| Автор: Akina 27.4.2016, 22:37 |
| Берёшь любой алгоритм поиска всех путей во взвешенном орграфе. Добавляешь отсев по длине и соответствию твоим доп. условиям. Всё. |
| Автор: Burka 5.5.2016, 09:53 |
| Волновой алгоритм http://algolist.manual.ru/games/wavealg.php https://habrahabr.ru/post/264189/ |