在无向连通图中，每条边都有一种颜色(红色、绿色或蓝色)。
有效路径是至少具有每种颜色的一条边的路径。
问题是如何找到最短的有效路径或确定不存在。
我尝试使用 BFS 但无法找到解决方案。
关于如何开始有什么想法吗？
最佳答案
首先，我假设颜色数量是固定的。 然后我会提出一个标签设置 Dijkstra 算法(与 Pareto Dijkstra 相比)，其运行时间为 O(n log(n) + m):
使用广义 Dijkstra 来查找最短路径: 每个节点都有一个标签列表，一个标签由起始节点的长度和尚未访问的所有颜色组成。 如果 (1) 它的长度较小并且 (2) 它包含另一个标签的所有颜色，则一个标签在该节点中占主导地位。被支配的标签直接被移除。 与 dijkstra 类似，您维护一个优先级队列，从中您始终可以放松长度较小的节点。取一条边到节点 v 将使标签的长度增加 endge 长度，并将边的颜色添加到标签中。该标签被添加到节点 v 的标签列表中。 当使用包含所有三种颜色的标签确定目标节点时，您已经找到了最短路径。 注意，如果要重构最后的最短路径，必须保存每个标签的前驱节点。
您从起始节点处的初始标签开始，其中包含 (0,{})(零长度且无颜色)。
每个节点对于每个颜色集组合最多可以结算一次，因为这种情况下只存在 8 个(固定)这样的组合，运行时间等于 Dijkstra 算法 最佳实现时间为 O(n*log(n)+m)。
关于computer-science - 彩边图中的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5370902/