Поиск кратчайшего пути в ориентированном графе с цветными вершинами и дугами?

Question

[cleerax]

Есть следующее задание:

Дан ориентированный граф с N вершинами (N < 50). Вершины и дуги окрашены в цвета с номерами от 1 до М (М < 6).
Указаны две вершины, в которых находятся фишки игрока, и конечная вершина.
Правила перемещения фишек: игрок может передвигать фишку по дуге, если ее цвет совпадает с цветом вершины,
в которой находится другая фишка; ходы можно делать только в направлении дуг графа;
поочередность ходов необязательна. Игра заканчивается, если одна из фишек достигает конечной вершины.
Написать программу поиска кратчайшего пути до конечной вершины, если он существует.

Сделал граф через матрицу смежности, где смежные вершины с разными цветами помечены разными цифрами. Алгоритм нахождения кратчайшего пути сделать не получается никак.
Подскажите, как вообще это можно сделать, или хотя бы скиньте каких-нибудь материалов, где про что-то похожее можно узнать, вроде этих двух игроков, цветных вершин и т. д.

Answer 1

[Wataru]

Тут надо сделать из графа на N вершин граф на N^2 вершин. Граф-то совсем маленький. Каждая вершина нового графа соответствует паре вершин изначалного графа (x, y) и обозначает, что фишки стоят в вершинах x и y соответственно. Переходы в новом графе делаются из переходов в изначальном: из (x, y) можно перейти в (x, z), если в изначальном графе есть дуга y->z и ее цвет совпадает с вершиной x. Аналогично из (x,y) можно перейти в (z,y), если есть дуга x->z и ее цвет совпадает с y.

В этом графе уже можно любым известным вам способом искать путь. Только тут конечных вершин будет сразу много: это все пары (x,y), где x или у - конечная вершина в графе. Можно или добавить новую конечную вершину и соединить с ней все вот эти вот, или прямо в алгоритме исправить условие останова.

Можно граф не хранить явно. Если у вас BFS, то храние в очереди сразу пару чисел. Внутри перебирайте переходы из первой а потом из второй вершины и делайте их только если условие на совпадение цвета выполняется. Ну и, все массивы хранящие расстояние и т.п. в алгоритме будут уже двумерные.