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

Question

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

Answer 1

如果我没理解错的话，您想要根据当前路径中访问的节点更改图中边的成本。评论中的一个例子是:

“边 AB 的长度为 3，但如果你也访问节点 C，则 AB 的长度将为 5”

现在，似乎没有办法使用像 Djikstra 算法这样的算法，因为该算法中有一个贪婪的步骤，可以在每个阶段选择“最佳”节点。那个点的“最佳”节点可能会在以后更改(由于上述规则)的概念违反了贪婪方法的概念，该方法假设我们正在按照从最佳到最差成本的顺序有效地访问节点。我不确定这是否像建议的那样是 NP 难，但它肯定不能从一开始就使用 Dijikstra 类方法。不过，为问题 +1。