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