algorithm - 具有最小成本约束下限的单源最短路径

Question

问题描述:

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

我知道在这种约束下，像 Bellman ford 这样的传统 SSSP 算法无法正常工作。我该如何找到解决这个问题的最有效算法？

Answer 1

我想你想散步，因为路径不能有循环。

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

找零问题:给定 N 种硬币，每种硬币的值为 c_i，是否有可能用这 N 种硬币来找零数 X？

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