У вас есть Honda Accord 2005 года с 50 милями (максимальный вес) в баке.Какие места McDonalds (узлы графа) вы можете посетить в радиусе 50 миль?Это мой вопрос.
Если у вас есть взвешенный ациклический ориентированный граф, как вы можете найти все узлы, которые можно посетить в рамках данного ограничения веса?
Мне известен алгоритм Дейкстры, но, похоже, я не могу найти документацию по его использованию за пределами мин-путей.В моем примере, нет конкретного узла, на котором мы хотим закончить, мы просто хотим пойти как можно дальше, не превышая максимальный вес.Кажется, что вы должны быть в состоянии использовать BFS / DFS, чтобы решить эту проблему, но я не могу найти документацию для реализации тех в графах с весами ребер (опять же, вне проблем min-path).