Если я правильно понимаю, вы хотите изменить стоимость ребра на графике в зависимости от узлов, которые посещаются на вашем текущем пути.Пример из комментариев:
"Edge AB имеет длину 3, но если вы также посетите узел C, длина AB будет 5"
Теперь, похоже, нетпуть для чего-то вроде алгоритма Джикстры, поскольку в этом алгоритме есть жадный шаг, который выбирает «лучший» узел на каждом этапе.Представление о том, что «лучший» узел в этой точке может измениться в более позднее время (из-за правила, такого как выше), нарушает концепцию жадного подхода, который предполагает, что мы эффективно посещаем узлы в порядке от наилучшей до худшей стоимости.Я не уверен, что это NP сложный, как предполагалось, но он, конечно, не может использовать подход Dijikstra с самого начала.+1 за проблему, хотя.