对于具有不同的必经节点集的最短路径，我可以使用哪种算法？

Question

我不确定这个问题的名称，所以没能真正研究它。我有一个完整的加权图，有一个开始和结束节点以及 n 个不同的节点集（我们称它们为红色、蓝色和绿色），每个节点有 m 个成员节点。

我需要找到从头到尾的最短路径，并且必须恰好通过一个红色、一个蓝色和一个绿色节点；有算法吗？

一个扩展是我需要找到最短路径，同时首先访问蓝色，然后是绿色，然后是红色（同样，每次访问恰好一次）；有这个吗？

Answer 1

扩展部分似乎更简单。

假设每个节点都有一种颜色（这是真的吗？）如果要删除会违反所需颜色序列的边，您需要做的所有事情。

例如，删除所有离开起点的边，除了那些去蓝色节点的边。同样，删除所有离开蓝色节点的边，除了那些去绿色节点的边。

然后你可以在缩减图上简单地运行一个标准的最短路径算法（例如Dijkstra）。

如果颜色的数量不是太多，那么你可以采用相同的算法来解决原来的问题。这个想法是为颜色的每个排列找到最短路径（使用上述算法）。