彩边图中的最短路径
在无向连通图中，每条边都有一种颜色（红色、绿色或蓝色）。
有效路径是至少具有每种颜色的一条边的路径。
问题是如何找到最短的有效路径或确定不存在。
我尝试使用 BFS 但无法找到解决方案。
关于如何开始有什么想法吗？
in undirected and connected graph, each edge has a color (red, green or blue).
a valid path is a path with at least one edge of each color.
the problem is how to find the shortest valid path or determine that none exists.
I tried to use BFS but could not figure out the solution.
any ideas on how to start?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
首先，我假设颜色数量是固定的。
然后我会提出一种标签设置 Dijkstra 算法（与 Pareto Dijkstra 相比），其运行时间为 O(n log(n) + m)：
使用广义 Dijkstra 来查找最短路径：
每个节点都有一个标签列表，一个标签由起始节点的长度和尚未访问的所有颜色组成。
如果 (1) 它的长度较小并且 (2) 它包含另一个标签的所有颜色，则一个标签在该节点中占主导地位。被支配的标签直接被移除。
与 dijkstra 类似，您维护一个优先级队列，从中您始终可以放松长度较小的节点。取一条边到节点 v 将使标签的长度增加 endge 长度，并将边的颜色添加到标签中。该标签被添加到节点 v 的标签列表中。
当使用包含所有三种颜色的标签确定目标节点时，您已经找到了最短路径。
请注意，如果要在最后重建最短路径，则必须保存每个标签的前驱节点。
您从起始节点处的初始标签 (0,{})（零长度且无颜色）开始。
每个节点对于每个颜色集组合最多可以结算一次，因为这种情况下只存在 8 个（固定）这样的组合，运行时间等于 Dijkstra 算法
最佳实现为 O(n*log(n)+m)。
First, i assume that the number of colors is fixed.
Then I would propose a label-setting Dijkstra algorithm (compare with Pareto Dijkstra) resulting in a running time of O(n log(n) + m):
Use a generalized Dijkstra to find the shortest path:
Each node has a list of labels, one label consists of a length from the start node and all colors yet visited.
One label dominates another label in this node if (1) it has less length and (2) it includes all colors of the other label. A dominated label is directly removed.
Similar to dijkstra you mantain a priority queue from which you relax always the node with less length. Taking an edge to a node v will increase the length of the label by the endge length and add the color of the edge to the label. The label is added to the list of labels of node v.
When settling the target node with a label containing all three colors, you have found the shortest path.
Note that you must save the predecessor node for each label if you want to reconstruct the shortest path at the end.
You start with an initial label at the start node with (0,{}) (zero length and no color).
Each node can be settled at most once per color set combination, as there exist only 8 (fixed) such combinations in this case, the running time is equal to Dijkstra's algorithm
which is O(n*log(n)+m) for the best implementation.
我将使用 BFS，从每个节点开始，计算从该节点可发现的第一个有效路径，保存该值，然后继续下一个。
该图可以用矩阵表示，每条边的颜色（例如，-1（无边）、0、1、2）作为该边在矩阵中的值。
当您发现路径时，可以将它们放入一对数组中，一个用于保留路径中的步骤，另一个用于检查三种颜色。
I would use BFS, and starting at each node, I would calculate the first valid path that is discoverable from that node, save that value, and move on to the next.
The graph can be represented in a matrix, with the color of each edge (say, -1 (no edge),0,1,2) as the value of the edge in the matrix.
The paths, as you discover them, can be put into a pair of arrays, one that keeps the steps in the path and one that checks off the three colors.
这个问题可以通过产品构造来解决。创建一个新的有向图，其中每个顶点都是原始图中的一对顶点和颜色的子集。 （因此，对于 3 种颜色，对于原始图中的每个顶点，新图中将有 8 个顶点。）如果原始图中的顶点与目标顶点之间有一条边，则在新图中的两个顶点之间添加一条边颜色集等于源顶点的颜色集加上原始图中的边颜色（如果颜色已在源顶点的颜色集中，则不会发生变化）。新边应与原始边具有相同的权重。
那么新图中从 (s, ∅) 到 (t, {red, green, blue}) 的最短路径对应于从 s 开始的最短路径 到 t 在使用所有 3 种颜色的原始图表中。由于新图中仅存在线性更多的顶点和边（假设固定颜色集），因此可以像普通的最短路径问题一样快地渐近解决该问题。
作为实现细节，请注意，无需在内存中实际写下整个产品图。顶点和边可以在运行最短路径算法时动态生成，这允许完全跳过未使用的顶点。
这种方法与eci的答案略有不同，因为它扩展了顶点标签而不是路径权重。
我在此处提出并回答了此问题的更一般形式。
This problem can be solved by a product construction. Create a new directed graph where each vertex is a pair of a vertex in the original graph and a subset of the colors. (So for 3 colors, there would be 8 vertices in the new graph for each vertex in the original graph.) Add an edge between two vertices in the new graph if there was an edge between the vertices in the original graph and the destination vertex's color set equals the source vertex's color set plus the edge color in the original graph (no change if the color was already in the source vertex's color set). The new edge should have the same weight as the original edge.
Then the shortest path in the new graph from (s, ∅) to (t, {red, green, blue}) corresponds to the shortest path from s to t in the original graph that uses all 3 colors. Since there are only linearly more vertices and edges in the new graph (assuming a fixed color set), this problem can be solved just as fast as an ordinary shortest path problem asymptotically.
As an implementation detail, note that there is no need to actually write down the whole product graph in memory. The vertices and edges can be generated dynamically while running the shortest path algorithm, which allows unused vertices to be skipped entirely.
This approach is slightly different to eci's answer in that it extends the vertex labels rather than the path weights.
I have asked and answered a more general form of this question here.
确实存在如下简单的解决方案。
假设没有颜色，在图表上做一个正常的 dijkstra。
猜出每种颜色的 3 条边。对于所有 m^3 可能的猜测，让边为 r1---r2 、 b1---b2、g1---g2 ，我们得到它们进入路径的 24 种可能的方式（8 种用于定向边的方式, 6 表示排列）。
由于您已经拥有正常的 dijkstra 数据，因此一旦完成此操作，您将在恒定时间内获得结果，从而最小化所有猜测。
对所有 n 个顶点重复此操作。
我确实同意最终复杂度 O(nm^3) 通常太大，但有时简单的算法会起作用。
There does exist a trivial solution as follows.
Do a normal dijkstra on the graph assuming no colors.
Guess 3 edges one of each color. For all the m^3 possible guessing let the edges be r1---r2 , b1---b2, g1---g2 we get 24 possible ways they can come in the path (8 for the ways you can orient the edges, 6 for the permutation).
Since you already have the normal dijkstra data, once you are done with this, you get in constant time the result, minimize over all guesses.
Repeat this for all n vertices.
I do agree that the finally complexity O(nm^3) is usually too large, but sometimes the trivial algorithm works.
创建一个新图形（6次），由原始图形的三个副本组成，第一个图形仅包含一种颜色的边缘，第二个图形还包含另一种颜色的边缘，并将它们与第二种颜色的边缘连接，第三个副本将具有所有边，并通过第三种颜色的边连接到第二个图。
然后运行 dijkstra 找到从 s1 到 t3 的最短路径。
因为我们不知道顺序是什么，所以我们将对所有 6 种可能的颜色顺序执行相同的操作，然后选择我们得到的 6 条最短路径中最短的一条。
to create a new graph (6 times) consists of three copies of the original one, the first one include only edges of one of the colors, the second one, includes also edges of another color, and connect them with edges from the second color, and the third copy will have all of the edges, and is connected to the second graph with edges from the third color.
then run dijkstra to find the shortest path from s1 to t3.
as we don't know what woul be the order we'll do the same thing for the whole 6 possible orders of the colors, and then choose the shortest of the 6 shortest paths we get.