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

Question

给定 G=(V,E) 每条边都具有这三种颜色中的一种 {green,red,blue}。如果一条路径包含所有三种颜色，我们将其称为“彩色路径”。

    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

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

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

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

从 s 到 t3(在 G3 中)运行 dijkstra。

我的解决方案正确吗？

Answer 1

我觉得不对。

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

对于彩色路径，您必须为每种颜色组合存储最短路径长度。所以，对于 3 种颜色，你必须存储最短的红色路径、最短的蓝色路径、最短的绿色路径，以及最短的红蓝、红绿和蓝绿路径，最后是最短的红绿-蓝色路径。 (共有 7 种颜色组合)。