Задачу решал исходя из того, что бы не менять и не подстраивать существующий граф под алгоритм, поэтому разбиение, удаление и т.п. делать не хотелось. Тем не менее задачу уже решил. Большинство предложенных вами алгоритмов я пробовал и ранее, и ни один  из них не смог корректно справится со всеми тестами на сильно извращенном графе. 

В любом случае с удовольствием гляну на чужую реализацию (вполне возможно я реализовал ее не оптимально).

P.S. Если перед кем нибудь стала похожая задача, пишите в icq (494107927), помогу с алгоритмом.

имеется ввиду, что на каком-то перекрестке нельзя поворачивать, например, направо с одной и только одной дороги.  см. пост выше:

yeputons, все именно так