Учитывая взвешенный, циклический, ориентированный граф и два узла, я ищу соединительный путь, общий вес которого максимально приближен к определенному значению, которое больше, чем самый короткий путь.
Пример из реальной ситуации: найдите маршрут из Вашингтона, округ Колумбия, в Нью-Йорк, длина которого составляет 400 миль, несмотря на то, что кратчайший путь составляет ~ 230 миль.
Все мои соображения до сих пор не оправдались по одной из следующих причин:
- Большинство алгоритмов маршрутизации, таких как Dijkstra, в этом случае не работают, потому что нет ничего, что можно минимизировать или максимизировать (расхождение данного веса с весом пути должно быть минимизировано, но вам нужен готовый путь для его вычисления)
- DFS и BFS можно использовать для поиска пути с определенным количеством прыжков (ребер), но он не учитывает взвешенные ребра