computer-science - 彩色边图中的最短路径

Question

在无向和连通图中，每条边都有一种颜色（红色、绿色或蓝色）。
有效路径是每种颜色至少有一条边的路径。
问题是如何找到最短的有效路径或确定不存在。

我尝试使用 BFS，但无法找出解决方案。
关于如何开始的任何想法？

Answer 1

首先，我假设颜色的数量是固定的。然后我会提出一个标签设置 Dijkstra 算法（与 Pareto Dijkstra 相比），运行时间为 O(n log(n) + m)：

使用广义 Dijkstra 找到最短路径：每个节点都有一个标签列表，一个标签由从起始节点的长度和尚未访问的所有颜色组成。如果 (1) 它的长度较短并且(2) 它包括其他标签的所有颜色。直接去除支配标签。与 dijkstra 类似，您维护一个优先级队列，您始终可以从该队列中放松长度较短的节点。对节点 v 取一条边会将标签的长度增加 endge 长度，并将边的颜色添加到标签中。标签被添加到节点 v 的标签列表中。当使用包含所有三种颜色的标签来设置目标节点时，您已经找到了最短路径。请注意，如果要在最后重建最短路径，则必须为每个标签保存前驱节点。

您从具有 (0,{})（零长度且无颜色）的起始节点处的初始标签开始。

每个颜色集组合每个节点最多可以解决一次，因为在这种情况下只有 8 个（固定）这样的组合，运行时间等于 Dijkstra 算法，即 O(n*log(n)+m)最佳实施。

Answer 2

我将使用 BFS，并从每个节点开始，计算从该节点可发现的第一个有效路径，保存该值，然后继续下一个。

该图可以用矩阵表示，每条边的颜色（例如，-1（无边）、0、1、2）作为矩阵中边的值。

当您发现路径时，可以将它们放入一对数组中，一个保留路径中的步骤，一个检查三种颜色。

Answer 3

这个问题可以通过产品构造来解决。创建一个新的有向图，其中每个顶点是原始图中的一对顶点和颜色的子集。（因此对于 3 种颜色，对于原始图中的每个顶点，新图中将有 8 个顶点。）如果原始图中的顶点与目标顶点的顶点之间存在边，则在新图中的两个顶点之间添加边颜色集等于源顶点的颜色集加上原始图中的边缘颜色（如果颜色已经在源顶点的颜色集中，则没有变化）。新边应与原始边具有相同的权重。

那么新图中从 ( s , ∅) 到 ( t , {red, green, blue}) 的最短路径对应于使用所有 3 种颜色的原始图中从s到t的最短路径。由于在新图中只有线性更多的顶点和边（假设一个固定的颜色集），这个问题可以像普通的最短路径问题一样快地渐近解决。

作为一个实现细节，请注意实际上不需要在内存中写下整个产品图。顶点和边可以在运行最短路径算法时动态生成，这允许完全跳过未使用的顶点。

这种方法与eci 的答案略有不同，因为它扩展了顶点标签而不是路径权重。

我在这里提出并回答了这个问题的更一般形式。

Answer 4

确实存在一个简单的解决方案，如下所示。

假设没有颜色，在图上做一个正常的 dijkstra。

猜测每种颜色的 3 条边。对于所有 m^3 种可能的猜测，让边缘为 r1---r2 , b1---b2, g1---g2 我们得到 24 种可能的方式，它们可以进入路径（8 种方式用于定位边缘, 6 为置换）。

由于您已经拥有正常的 dijkstra 数据，因此一旦完成此操作，您就会在恒定时间内得到结果，最小化所有猜测。

对所有 n 个顶点重复此操作。

我同意最终复杂度 O(nm^3) 通常太大，但有时微不足道的算法可以工作。

Answer 5

创建一个新图形（6 次）由原始图形的三个副本组成，第一个仅包含一种颜色的边，第二个包含另一种颜色的边，并将它们与第二种颜色的边连接，并且第三个副本将具有所有边，并使用来自第三种颜色的边连接到第二个图。然后运行 ​​dijkstra 找到从 s1 到 t3 的最短路径。因为我们不知道顺序是什么，所以我们将对全部 6 种可能的颜色顺序做同样的事情，然后选择我们得到的 6 条最短路径中最短的一条。