Когда вы идете по пути от s до v , go из одного «состояния» в другое, где «состояние» включает оба узла, на которых вы находитесь и , какие цвета узлов вы посетили в своем путешествии (7 возможных комбинаций). Ваше состояние определяет, какие пути от вашей текущей позиции являются допустимыми решениями.
Из исходного графика создайте (или представьте) график доступных состояний, где ребро представляет возможность перехода из одного состояния в другое. Этот граф будет иметь до 7 вершин для каждой из исходных вершин графа.
Теперь используйте алгоритм Дейкстры, чтобы найти кратчайший путь от (s, красный) (при условии, что s - красный) до ( V, красный + зеленый + синий)