Return to Revisions

DFS can be implemented with slight backtracking but it is not feasible , on a unweighted going with bfs is better since it moves level by level.

DFS code:

void shortestPathDFS(vector<vector<int>>& graph, int current, int destination, vector<int>& path, vector<int>& shortestPath, unordered_set<int>& visited) {

visited.insert(current);

path.push_back(current);

if (current == destination) {
    if (shortestPath.empty() || path.size() < shortestPath.size()) {
        shortestPath = path;
    }
     return;
}

for (int neighbor : graph[current]) {
    if (visited.find(neighbor) == visited.end()) {
        shortestPathDFS(graph, neighbor, destination, path, shortestPath, visited);
    }
}

path.pop_back();
visited.erase(current);

}