Как модифицировать алгоритм Ли для куба?

Question

[Николай Шепелев]

Есть алгоритм Ли - алгоритм поиска кратчайшего пути на планарном графе (Wiki).
Как можно модифицировать алгоритм Ли для куба (т. е. для его развертки), без особых потерь в производительности?

Comments

[Александр Скуснов]

вы делаете трассировку плат? Обычно берут 4 слоя: плюс, минус, вертикальные и горизонтальные дорожки. Последние два слоя с переходами. Это не поможет?

[Николай Шепелев]

Нет, не трассировка плат. Здесь чисто алгоритмически нужно решить задачу. Мне нужно найти кратчайший путь на кубе, каждая грань которого разбита на ячейки. Идти можно только по этим ячейкам (при этом только через грани ячейки - ортогональный путь).

[Sayonji]

Алгоритм Ли это обычный поиск в ширину. И для развёртки куба он будет работать без проблем.