具有最小费用下界约束的单源最短路径

Question

问题描述：

给定adjacencyMatrix和adjacencyList中的一个图G，其中有一个源顶点s和一个目的顶点d。找出从s到d的带约束的最短路径。约束是最短路径成本c具有下界，即成本c必须大于分配的下界N，但在大于或等于N的所有可能路径的成本中是最小的。

我知道有了这个限制，像Bellman ford这样的传统SSSP算法不能正常工作。我该如何为这个问题找到最有效的算法呢？

Answer 1

我猜你想要走一走，因为path不能有循环。

不幸的是，这个问题可以很容易地建模为改变问题，这也是NPC。

找零问题:给定N种类型的硬币，每种硬币的c_i值，有没有可能用这N个硬币改变数字X？

建模:假设所有的c_i都是偶数(所有c_i都加倍，如果不是，也是X )。创建N +2个顶点，第i个顶点表示1 <= i <= N的第i个硬币。此外，(N+1)和(N+2)-th顶点对所有成本为(c_i / 2)的硬币都有边。那么这个问题就等同于找到一条成本至少为X的最短路径，这就是NPC。减少应该是显而易见的，但如果需要进一步的解释，我可以编辑我的答案。