algorithm - 对于每个节点 v：找到从 s 到 v 的更便宜的彩色路径

Question

令 G = (V,E)，其中每个节点具有三种颜色 {R, G, B} 中的一种。

如果路径（不一定简单）包含所有颜色，则将其称为彩色。

输入：如上的有向图 G（包括每个节点的颜色），s∈V，和正权重 w：E → Q。

输出：对于每个节点 v：找到从 s 到 v 的更便宜的彩色路径（不一定简单） （如果不存在则返回无穷大）。

标签： algorithm

Answer 1

您可以使用Dijkstra 算法的修改形式从节点开始执行此操作s。对于找到的每条路径，跟踪迄今为止在该路径中使用了哪些颜色；当将路径的延续插入优先级队列时，新路径可能包括一种附加颜色。在更新节点处的“最佳”路径时，可能有多个“最佳”路径，因为两条路径可能使用不同的颜色，或者一条路径可能更短但使用的颜色更少。

这看起来像是一个家庭作业问题，所以我将把其余的细节留给你自己解决。