algorithm - 最小 RGB 路径

Question

您将获得一个有向图G = (V, E) 加权边。节点颜色为红色、绿色和蓝色。如果一条从s到v的路径包含红绿色和一个蓝色节点，则该路径称为彩色路径。

找到s和每个v之间的最短路径，条件是路径应该是彩色的。如果有不止一条色彩缤纷的路径，请找到它们之间的最小值。

如果没有这样的路径返回 false。

我不知道如何开始。任何帮助是极大的赞赏！

标签： algorithmgraph

Answer 1

当您沿着从s到v的路径行走时，从一个“状态”到另一个“状态”包括您所在的节点以及您在旅途中所使用的节点颜色（7 种可能的组合） . 您的状态决定了您当前位置的哪些路径是有效的解决方案。

从您的原始图表中，制作（或想象）一个可访问状态的图表，其中一条边表示从一个状态转换到下一个状态的能力。该图对于每个原始图顶点最多有 7 个顶点。

现在使用 Dijkstra 算法找到从(s,red)（假设 s 是红色）到 ( v,red+green+blue)的最短路径