algorithm - 带彩色边的图 : shortest paths with at most k color changes?

Question

我有一个带有彩色加权边的有向图。有2种颜色。每条边只能有一种颜色。我想找到颜色变化有限的最短路径。从一个顶点开始，最多可以有 2 strip 2 种不同颜色的边和 2 strip 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) 的渐近运行时间。

希望这对您有所帮助!