使用Dijkstra或Bellman – Ford的算法修改的最短路径

Question

我们如何使用Dijkstra或Bellman – Ford的算法在图中找到最短的路径，如果我们转到特定的顶点，其某些边缘会受到影响。这样，受影响的边缘的长度将超过或小于原始长度。

Answer 1

如果我理解正确的话，您想根据当前路径中访问的节点来更改图表中的优势成本。评论中的一个示例是：

“ Edge AB有3个长度3，但是如果您也访问Node C，AB的长度将为5”

现在，似乎没有一种方法可以使用Djikstra的算法，因为该算法中有一个贪婪的步骤，它在每个阶段都选择了“最佳”节点。当时的“最佳”节点可能会在以后的时间发生变化（由于上述规则）违反了贪婪方法的概念，该方法假设我们正在有效地访问节点，以便从最佳到最差的成本到最佳成本。我不确定这是否是NP的建议，但是从一开始就不能使用Dijikstra的方法。 +1解决问题。