Модифицированный кратчайший путь с использованием алгоритма Dijkstra или Bellman -Ford

Question

Как мы можем использовать алгоритм Dijkstra или Bellman -Ford, чтобы найти самый короткий путь на графике, некоторые из ребра влияют, если мы перейдем к конкретным вершинам. Такой, что длина пораженного края будет более или меньше, чем исходная длина.

Answer 1

Если я понимаю это право, вы хотите изменить стоимость края на графике в зависимости от узлов, которые посещаются на вашем текущем пути. Пример из комментариев:

"Edge AB имеет длину 3, но если вы также посетите узлы C, длина AB будет 5"

Теперь, кажется, нет способа, как что -то вроде алгоритма Djikstra, который будет использоваться, поскольку в этом алгоритме есть жадный шаг, который выбирает «лучший» узел на каждом этапе. Представление о том, что «лучший» узел в этот момент может измениться в более позднее время (из -за правила, такого как выше), нарушает концепцию жадного подхода, который предполагает, что мы эффективно посещаем узлы в порядке от лучших до худших затрат. Я не уверен, что это трудно, как предложено, но он, конечно, не может использовать подход диджикстра с самого начала. +1 для проблемы, хотя.