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

Question

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

Answer 1

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

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

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