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) 。