Algorithm: Shortest path (walk) with keys and doors

Question

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.

---

Update

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.

Answer 1

This other question about mazes is closely related. It deals with the simpler problem of having to collect each of the items before leaving the maze. One can make the analogy that there is a single door at the end of the maze, but it has a very complicated lock and you must collect all the keys to get through it.

The complexity depends on the structure of the maze. In particular, my answer to the other question proves that, if the maze is a general graph, the collect-all-the-items version of the problem is NP-complete and, in fact, the same holds for planar graphs. This means that your problem is also NP-complete on general (or planar) graphs. Here's a sketch of the reduction. You simulate the door with the complicated lock by replacing the exit to the maze with a very long passage that ends with the $k$ doors one after another. You make the passage long enough that the optimal solution is definitely to collect all the keys first and then walk down that passage and unlock the doors, because walking back and forth between keys and doors would simply be too long. Now the hardness of the collect-all-the-items problem implies that your problem is hard, too.

If your maze is a tree, the problem might be easier – the collect-all-the-items version has a polynomial-time algorithm in that case. And, in any case, the more general problem being NP-complete doesn't mean there aren't more efficient algorithms than brute force: but it does mean you shouldn't expect a polynomial-time algorithm.

Answer 2

It is a homework, so I will not give a full answer.

The update (that $k$ is a constant) is the key to an efficient algorithm.

Suppose further, that the order in which the keys are collected is fixed. Then you have to find a path from the start to the first key, from there to the second key, from there to the third key and so on. Doors may olny be passed in path segment which occur after collecting the respective key.

Try to find an algorithm for that further restriction, then solve the general case.