找到图中颜色最少的路径

Question

我试图解决的问题是这样的：

给定一个图 G = (V,E)，其中每条边都用 10 种颜色之一着色，并且有两个顶点：s、t。

我需要找到一种算法，可以生成从 s 到 t 的（最短）路径，并且经过最少量的颜色。

我的想法是将图表复制 10 次：

第一个副本将仅包含一种颜色的边缘

第二个将仅包括两种颜色的边缘......依此类推。

另外，我将一个外部节点：s' 连接到每个副本中的每个“s”节点。

但是，我突然想到，对于这种方法，我需要复制图表不是 10 次，而是大约 10 次！（或者甚至可能是 2^10？）每种颜色组合的次数。

那么解决这个问题的有效算法是什么？

Answer 1

我不相信有一个简单的算法可以解决这个问题，因为这个问题的一般形式是 NP 难的。也就是说，在任意颜色的图中，找到接触最小颜色集的两个顶点之间的最短路径是 NP 困难的。

因此，虽然可能有稍微更好的算法，但您解决图形的 1024 个变体（10 种颜色的每个子集一个）的想法可能是合理的。

证明

该证明的工作原理是减少其命中集问题。命中集问题是 NP 完全问题，因此对问题的简化表明您的问题是 NP 难问题。

回想一下，命中集问题需要集合 X1...Xn，每个集合都包含来自某个宇宙 U 的元素，并且要求找到一个最小集合 {x1, ..., xk}，这样对于所有 i，有 aj 使得 xj在奚。

图中的颜色将是 U 的元素。设图本身由 n+1 个顶点组成。这些将是 X0（一个起始节点，命名只是为了下面符号方便）和代表 X1 ... Xn 的顶点。

对于 Xi+1 中的每个 x，用颜色 x 的边将 Xi 连接到 Xi+1。

然后，在此图中，从 X0 到 Xn 的所有路径的长度均为 n，但使用最少颜色数的路径恰好对应于最小命中集。

请注意，这扩展了图的定义以包括节点之间的多条边。如果这不行，那么就在构造图的每条边的中间添加一个额外的节点。