I'm trying to solve the following algorithm question:
A maze is given by a graph (with let's say $v$ vertices and $e$ edges), where $k$ vertices are different keys and, $k$ vertices are the corresponding doors (there is always one key for a single door) and one vertex is the end of the maze. Find the shortest path (it's actually a walk because it makes sense to move back after a key is found) from a given vertex to the end.
I should note that it is a homework for a class, where only DFS and BFS graph traversing algorithms were used so far, so it should be possible to solve this using only these two algorithms to search the graph.
My approach so far:
I've tried a recursive DFS (to better keep track of the current path and all the keys found on it) with a concept of multiple levels of "found vertices" - when a key is found, the previously found vertices are saved for later use, but at current iterations, it continues as if no vertices were found. When the current recursive call ends, the algorithm moves back a few vertices, when it removes a key it gets back to the previous level of found vertices.
This algorithm should be possible to use but I found it quite hard to figure out the asymptotic time complexity.
Then I realized that it could be simplified. First, do a BFS from the start node (that's $O(v+e)$), get the shortest paths to the keys and to the end and make a new graph of these shortest paths. Then do a BFS again from the first key (some doors could have opened, so it makes sense to search it all over again), get the shortest paths to all other keys and to the end and add these to the graph. Continue for the rest of the keys. At the end do a BFS on the new graph again.
The problem is with the "Continue for the rest of the keys" part, as there are $k!$ ways to collect the keys in different orders, and the new graph would have something like $1+k+k(k-1)+\cdots+k!+k!$ vertices.
Is there any way not to check all the possible permutations? It seems to me, that you can never know, whether there is a possibility of a better path before collecting the keys in a different order.
After submitting the solution, the teacher said, that $k$ was meant as a constant, not the input, so the goal was to minimize the time complexity relative to $v$ and $e$ after all.