I wrote a program that solves maze that is not ideal (has 1 or more correct paths) using recursion DFS algorithm. I have a problem with the time complexity of my program, becouse i read on the internet that the time complexity for DFS is O(v+n) where n is the number of node and v the number of edges. In my case if i don't find the correct path i go back and go the other bath if there is a branching, so i am thinking how it will affect my time complexity. NOTE(mazes that i use are directed graph, so i can't go back and have to go from up to down)
void DFS3 (int *visited, double **graf, int *paths, int **results, int n, int v, int end){
visited [ v ] = 1;
if(v==end){ // if we find the end we write the table of paths (our path) to the table of results
results[r][0]=k+1;
for(int j=1;j<k+1;j++)
results[r][j]=paths[j-1];
results[r][k+1]=end; // we write the last node (our wayout) to the table of results (it's not included in table of path)
r++;
visited[v]=0; // we mark the last node as not visited
}
for(int i = 1; i < n*n+1; i++ ){
if( ( graf [ v ][ i ] != 0 ) && visited [ i ] != 1 ){
paths[k]=v; // if we find the connection between node (a path) we write it to the paths and run the DFS3 of this node
k++;
DFS3 ( visited, graf, paths,results, n, i, end);
}
}
paths[k]=0; // if there is a dead end we go back to the first branching and delete the nodes that aren't correct path
k--;
visited[v]=0; // we mark them as unvisited
}
In DFS, as long as you are marking the nodes as already visited, you can avoid visiting them again. So, while you still have to evaluate all the edges (and there can be O(|V|^2 many directed edges), you don't have to go back down old paths.
If you want the shortest path through the maze (and not just the first one you happen to find), DFS is not great since you'd need to let it keep running to find all paths, then choose the shortest one. BFS will get you the shortest path first, but almost surely take longer to find a path through than DFS would. But, it's also O(|V| + |E|)