Multiple Source Multiple Destination shortest path

Question

Let's say we have a maze, which has a width of W and a height of H. In this maze there are multiple people and multiple towers. The people are the sources (S) and the towers (D) are the destinations. It should be known that we have an omniscient view of the maze. My question is then this:

If I want to find the shortest path between any of the different SD combinations, how do I go about this?

At first, I can think of a naive solution that involves breaking this down into SD different OSOD operations, the problem is that this is quite time-consuming.

The second option would be to break it down into S different OSMD operations. But this I suspect is still too time inefficient for what I'm looking for.

I need an algorithm that can perform the pathfinding in O(WH) time. I've not been able to find anything that gives me the shortest path in O(WH) time and which is MSMD based. Hopefully, someone can point me in the right direction.

Answer 1

Imagine a graph that includes the maze as well as start and end vertexes outside the maze, with an edge from the start vertex to every S, and an edge from every D to the end vertex.

Now breadth-first search (since there are no weights) to find the shortest path from the single start to the single end.

I say 'imagine' that graph, because you don't actually have to build it. This ends up being a simple breadth-first search with minor modifications -- you start with all the S nodes in the root level, and stop when you reach any D.