带有彩色边缘的图形:最短路径,最多k个颜色变化？

Question

我有一个带有彩色加权边的有向图.有2种颜色.每个边缘只能有1种颜色.我想找到颜色变化有限的最短路径.从一个顶点可以出现最多2个边缘,其中有2种不同的颜色,2个边缘有2种不同的颜色.

例如,在此图中:

最短路径最多3个颜色变化将是9 最大0颜色变化最短路径6+1+4=11等.

我的解决方案是递归访问所有可能的路径并交换,如果递归找到一个更好的,使这个问题呈指数级.

是否存在针对此问题的非指数解决方案？

Answer 1

这可以通过在适当构造的图上运行Dijkstra算法在时间O(nm + n ² log n)中求解.

为了激发我们前进的直觉,让我们假设最佳路径最多只能产生一种颜色变化,并从红色边缘开始.因此,路径不遵循蓝色边缘,在这种情况下,我们只跟随红色边缘,或者它遵循一定数量的红色边缘,然后是一些蓝色边缘.

想想如果你按如下方式变换G会发生什么:

• 首先将图形中的节点复制两次,得到两层G0和G1.我们将G0中的节点v的副本表示为v0,将G1中的节点v的副本表示为v1.
• 对于每个蓝色边缘(u0,v0),用边(u0,v1)替换该边.
• 从G1中删除所有红色边缘.

您可以将此图表视为G的两个副本堆叠在一起,并对边缘进行一些调整.具体来说,在G0内部运行的边缘都是红色,蓝色边缘将您带到G1.G1中没有红色边缘.

想想这个图表中的路径是什么样的.如果你纯粹保持在G0,它只包含红色边缘.如果从G0开始并以G1结束,那么路径开始是通过跟随一些红色边缘,然后是至少一个蓝色边缘,然后是一些更大数量的蓝色边缘.因此,此图中的任何路径都只包含一个颜色变化.

您可以使用此图来查找从节点u到节点v的最短路径,该路径最多只能进行一次颜色更改.首先运行从u开始的Dijkstra算法,然后查看v0和v1的距离.到v0的距离是到v0的最短路径的长度,没有颜色变化.到v1的距离是到v1的最短路径的长度,最多可以产生一次颜色变化.这两个距离中较短的距离为您提供从u到v的最短路径的长度,最多可以产生一种颜色变化.

我们可以扩展这个技巧以适用于任何数量的步骤k,如下所示.创建G的k个副本,称为G0,G1,G2,...,G(k-1).假设路径以红色边缘开始,我们可以按如下方式更改图形.使G0中的所有蓝色边缘从G0运行到G1.然后,使G1中的所有红色边缘从G1运行到G2.然后,使G2中的所有蓝色边缘从G2运行到G3等.最后,删除G(k-1)中不是通向G(k-1)的颜色的所有边缘.该图保持与以前相同的属性 - 从节点u0到节点v_r的任何路径表示从u到v的路径,其精确地进行r颜色变化,假设第一个边是红色.然后,通过查看到v_0,v_1,...,v_(k-1)的路径的最低成本,可以找到最多产生r颜色变化的最佳路径.

到目前为止,这种方法假设第一步是红色,但我们不能保证是这种情况.但是没关系 - 我们可以运行这个算法,假设第一步是红色,一旦假设第一步是蓝色,并采取两个选项的最佳.

那么这有多贵？好吧,如果我们得到最多k个颜色变化,我们构造的图将具有总共O(nk)个节点和O(mk)个边缘,因此构造它将花费时间O(k(m + n)).在图中运行Dijkstra以找到到达所有目标节点的最短路径然后花费时间O(mk + nk log nk),因此总运行时间为O(mk + nk log nk).

我们实际上可以在O(mn + n ² log n)处将其上限,原因如下:由于所有边都具有严格的正权重,因此我们知道没有路径可以产生超过n - 1个颜色变化.如果一个路径,它将至少有n个边,所以它将有一个循环.这个周期具有严格的正成本,因此我们可以通过消除周期来提高成本.因此,如果k≥n,我们可以将k上限设为n.将k = n插入上述表达式得到O(mn + n ² log n)的渐近运行时间.

希望这可以帮助!