Алгоритм першого шляху глибини лабіринт з використанням рекурсії - c ++, алгоритм, рекурсія, лабіринт

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

Я шукав по всьому Інтернету, і більшість результатів тільки Dijkstra алгоритм, який не рекурсивний.

Дякую.

Відповіді:

Чому потрібно використовувати рекурсію? Найпростішим алгоритмом пошуку найкоротшого шляху є BFS, а не DFS, і він не рекурсивний. Я не знаю жодного хорошого і швидкого алгоритму найкоротшого шляху, який використовує рекурсію.

Але також зверніть увагу, що якщо ваш граф (лабіринт) є a деревоне має циклів, тоді з кожної вершини один до одного є тільки один шлях, і це буде найкоротшим, тому DFS буде застосовним в цьому випадку.