Здравствуйте AndrewVK, Вы писали:

AVK>Зависит от характеристик графа. В общем случае — волновой алгоритм по графу с глобальным графом строящимся на основании пройденных вершин.

То есть ты предлагаешь брать каждую вершину и проверять достижима ли она через другие вершины?
Если так,то это очень долго — а как-нибудь по быстрее.
О графе известно: список вершины, и матрица единичной достижимости (граф планарный).