algorithm - 具有另一个约束的最短路径

Question

给定一个带权无向图，我需要找到两个节点之间的最短路径，实际上是一个经典的最短路径问题。但是还有一个约束:每个节点包含一个“减少”值，可以用来减少一次遍历的后续边的成本(不仅相邻，而且减少不是累积的)。因此，您可以使用之前经过的节点之一中的“减少”来降低边的成本(每条边的最终成本不能小于 0)。

请注意，一旦我们通过缩减遍历了一个节点，我们就可以再次将其用于所有后续边(不仅是相邻的，而且它的可用时间不受限制)。减少不会累积。

让我们考虑这张图:

在此图中，从节点 1 到节点 5 的最短路径是:

• 1 -> 4 的成本为 13 (15-2)
• 4 -> 3 成本为 0 (12-12)
• 3 -> 5 成本为 0 (10-12) 在这种情况下，我们重用节点 4 的缩减，因为它大于节点 3 的缩减(我们遍历节点 n°4 然后我们有无限减少成本 12).它是 0 而不是 -2，因为边的权重不能为负。

那么从节点1到节点5的总花费是13 + 0 + 0 = 13

为了解决这个问题，我试过使用经典的 Dijkstra/Bellman-Ford 但它没有用，你能帮我解决这个问题吗？

Answer 1

这似乎可以通过 Bellman-Ford 的变体来解决。

到给定节点的每条路径都可以总结为一对 (C, D)，其中 C 是该路径的成本(折扣后)，D 是该路径上可用的最佳折扣因子。由于一旦访问该节点，折扣就可以无限次重复使用，因此始终使用迄今为止在该路径上看到的最大折扣是有意义的。例如，路径 (1 -> 4 -> 3) 的成本 C = 13，折扣 D = 12。

未折扣问题的复杂之处在于，我们无法从成本中判断到源和目标之间的节点的“最佳”路径是什么。在您的示例中，路径 (1 -> 2 -> 3) 的成本低于 (1 -> 4 -> 3)，但后者具有更好的折扣，这就是为什么从 1 到 5 的最佳路径是 (1 -> 4 -> 3 -> 5).

我们不需要记录到每个节点的最低成本路径(在 Bellman-Ford 算法中)，我们需要记录到目前为止找到的从源到该节点的所有“可行”路径。如果没有其他已知路径具有更低的成本和更好的折扣，则可以说一条路径是可行的。算法终止后，我们可以从源到目的地的所有可行路径中选择成本最小的路径，忽略折扣。

(编辑:我最初建议可以使用 Djikstra，但我认为这不是那么简单。我不确定我们是否可以以任何有意义的方式选择“最近的”未访问节点，以便我们保证找到最小路径。其他人可能会看到如何让它工作......)