我有一个具有 2n 个顶点的图，其中每条边都有定义的长度。看起来像**
**。
我试图找到从u到v的最短路径的长度(边长的最小总和)，有两个额外的限制:
- 路径包含的蓝色边的数量与红色边的数量相同。
- 路径包含的黑边数量不大于p。
我想出了一种我认为可行的指数时间算法。它按以下方式迭代表示从 u 开始的路径的长度 n - 1 的所有二进制组合:
- 0 是蓝色边缘
- 1 是红边
- 每当出现黑边
- 该组合以1开头。第一条边(来自 u)就是左侧的第一个黑色边。
- 该组合以0结尾。那么最后一条边(到v)就是右边最后一个黑色的边。
- 相邻数字不同。这意味着我们从蓝色边缘变为红色边缘(反之亦然)，因此中间有一个黑色边缘。
该算法会忽略不满足前面提到的两个要求的路径，并计算满足的路径的长度，然后找到最短的路径。然而，这样做可能会非常慢，我正在寻找一些技巧来提出更快的算法。我怀疑可以通过动态编程来实现，但我真的不知道从哪里开始。任何帮助将不胜感激。谢谢。
最佳答案
看起来像Dynamic Programming对我来说是个问题。
In here, v,u are arbitrary nodes.
Source node: s
Target node: t
For a node v, such that its outgoing edges are (v,u1) [red/blue], (v,u2) [black].
D(v,i,k) = min { ((v,u1) is red ? D(u1,i+1,k) : D(u1,i-1,k)) + w(v,u1) ,
D(u2,i,k-1) + w(v,u2) }
D(t,0,k) = 0 k <= p
D(v,i,k) = infinity k > p //note, for any v
D(t,i,k) = infinity i != 0
说明:
- v - 当前节点
- 我 - #reds_traversed - #blues_traversed
- k - #black_edges_left
停止子句位于目标节点，到达目标节点时结束，并且仅允许 i=0 且 k<=p
递归调用在每个点检查“哪个更好？穿过黑色还是穿过红色/蓝色”，并从两个选项中选择最佳解决方案。
这个想法是，D(v,i,k)是从v开始的最佳结果到目标(t)，#reds-#blues使用的是 i ，您最多可以使用 k黑色边缘。
由此，我们可以得出D(s,0,p)是从源头到达目标的最优结果。
自 |i| <= n, k<=p<=n - 算法的总运行时间为 O(n^3) ，假设以动态规划实现。
关于c++ - 查找图中的最短路径，有附加限制，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33509276/