Алгоритм самого длинного пути с "может" имеет цикл и отрицательный фронт на определенном шаге
Я провел собственное исследование, однако не смог найти правильного решения для своего требования.
Проблема в том, что у меня есть грузовик, который должен тратить груз (скажем, мусор). Существуют города (узел) и ребра (путь), которые могут быть положительными или отрицательными. В то время как грузовик идет своим путем, он может потерять или получить больше (отходы) зависит от выбранного пути (преимущество). Если он выбрал положительное ребро, он потеряет отходы точно в том же количестве, что и выбранное значение пути. И наоборот.
Таким образом, водитель грузовика должен сделать определенное количество шагов (каждый шаг занимает постоянное время независимо от значения ребра), а у водителя есть ограниченное время, чтобы вернуться домой (исходный узел)(время будет заданным параметром)
Таким образом, в этом графе у нас есть узлы, у нас есть ребра, направление которых одно, это ребро может иметь отрицательное или положительное значение, а в графе могут быть циклы, драйвер которых разрешено использовать или не использовать. И узлы могут указывать друг на друга разными краями. (от A до B ребро val равно 5) (от B до A ребро val равно -3 и так далее..)
Поэтому я хочу дать водителю наилучший способ потратить максимальную нагрузку в максимально короткие сроки.
Итак, проблема заключается в следующем.
То, что я хочу, обратите внимание на фактический код.
Если вы знаете название проблемы, которую можете указать, добро пожаловать. Если вы хотите поделиться своим собственным алгоритмом с псевдокодом или просто словами. Всегда пожалуйста. Если вы хотите поделиться ссылкой, по вашему мнению, возникает аналогичная проблема. Добро пожаловать.
И если вы думаете, что это невозможно решить. Пожалуйста, поделитесь своими мыслями или ссылкой, которая доказывает.
Заранее спасибо.