Рекурсивный шаблон DFS для поиска кратчайшего пути

Question

Я изучаю DFS через dfs-template I - LeetCode

Введен шаблон рекурсии

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

Вопрос, поднятый в конце

В приведенном выше шаблоне мы останавливаемся, когда находим путь first.

Что если вы хотите найти путь shortest?

Подсказка: добавьте еще один параметр, чтобы указать кратчайший путь, который вы уже нашли.

Как найти кратчайший путь?

Я предполагал, что следует добавить параметр step, чтобы запомнить depth каждого поворота для прохождения, после того, как исчерпаны все возможные пути, сравните глубины и верните минимальное значение.

Где находится параметр step?

Answer 1

distances = new int[numberOfNodes];
boolean DFS(Node cur, Node target, Set<Node> visited, level) {
    for (next : each neighbor of cur) {
        if (next is not in visited and level + 1 < distances[next]) {
            distances[neighbor] = level + 1
            add next to visted;
            DFS(next, target, visited, level + 1)
        }
    }
    return false;
}

массив массивов будет хранить кратчайший путь для каждого узла