小编jac*_*son的帖子

我有一个带有2n个顶点的图形,其中每个边都有一个定义的长度.看起来像**

**.

我试图找到从u到v的最短路径的长度(边长的最小总和),还有2个额外的限制:

• 路径包含的蓝色边数与红色边数相同.
• 路径包含的黑边数不大于p.

我想出了一个指数时间算法,我觉得它可行.它遍历所有长度为n-1的二进制组合,它们表示从u开始的路径,方式如下:

• 0是蓝色边缘
• 1是红色边缘
• 每当有黑边
  • 组合从1开始.然后第一个边缘(来自u)是左边的第一个黑色边缘.
  • 组合以0结尾.然后最后一个边缘(到v)是右边的最后一个黑色边缘.
  • 相邻的数字是不同的.这意味着我们从蓝色边缘变为红色边缘(反之亦然),因此中间有一个黑色边缘.

该算法将忽略不符合前面提到的2个要求的路径,并计算那些路径的长度,然后找到最短的路径.然而,这样做可能会非常慢,我正在寻找一些提示,以提出更快的算法.我怀疑用动态编程可以实现,但我真的不知道从哪里开始.任何帮助将非常感激.谢谢.