如何找到最短的彩色路径？

Question

给定 G=(V,E) 每条边都具有这三种颜色之一 {green,red,blue}。如果他拥有所有三种颜色，我们称路径为 "Colored Path"。

    Input: graph G(V,E),weight function w:E->Q+ , colored edges and vertices s .
    output: algorithm that finds for every vertices v, a shortest path from s 
           that is Colored path

我的解决方案是遍历图形，并为每个顶点计算路径具有的颜色数。创建名为 G1,G2,G3

的图形的 3 个副本

对于 c(v) = 2 的每个 v（c 是从 s 到此路径的颜色数），在第二个图 (G2) 中将 v1 连接到 v2，边权重 = 0。

对于每条边 c(v)= 3 从 v2（从 G2）连接到 v3（到 G3），边权重 = 0。

运行 dijkstra 从 s 到 t3（在 G3 中）。

我的解决方案对吗？

Answer 1

我觉得不对。

最简单的方法是认识到在正常的 Dijkstra 中，每个节点中只有一个重要的东西要存储，那就是从根开始的绝对最短路径长度。

对于彩色路径，您必须为每种颜色组合存储最短路径长度。因此，对于 3 种颜色，您必须存储最短的红色路径、最短的蓝色路径、最短的绿色路径，以及最短的 red-blue、red-green 和 blue-green 路径，以及最后是最短的 red-green-blue 路径。（共有 7 种颜色组合）。

如何找到最短的彩色路径？

How to find the shortest colored path?

algorithm

shortest-path