Алгоритм первого пути лабиринта с использованием recurssion

Question

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

Я смотрю по всему Интернету, и большинство результатов - это алгоритм Дейкстры, который не является рекурсивным. Может ли кто-нибудь указать псевдокод или указать мне в правильном направлении?

спасибо.

Answer 1

Зачем вам нужна рекурсия? Самый простой алгоритм поиска кратчайшего пути - BFS, а не DFS, и он не является рекурсивным. Я не знаю хорошего и быстрого алгоритма кратчайшего пути общего случая, который использует рекурсию.

Но также отметить, что если ваш график (лабиринт) является деревом, т.е. не имеет циклов, то из каждой вершины друг к другу есть только один путь, и это будет самым коротким, так ДФС будет применяться в Это дело.