Interview: Find shortest path to few elements

Question

There is a museum organized as NxN room. Some rooms are locked and inaccessible. Other rooms are open and some rooms have guards. Guards can only move north, south, east and west, only through open rooms and only within the museum. For each room, find the shortest distance to a guard. What is the time complexity of your algorithm?

Answer 1

You just need to look at that museum as one graph and use the Dijikstra algorithm.

wiki link

You have a discussion about complexity on the given page.

Answer 2

You can find Dijkstra's shortest path algorithm implemented in this series of posts:

Breadth and depth first search

Answer 3

As a start, consider a relatively naive approach.

With each guard G as a vertex in the set of rooms, R=N*N, and possible paths between adjacent rooms (edges) E.

If all room minimum distances must be known, BFS from each guard to each room.

This should take time G * (R+E), or something like G*(N*N+E), or G*(N*N).

This can certainly be optimized with memoization, as each BFS will be computing subtrees repeatedly that have already been completed. Depending on the room configuration, this could greatly reduce G from the above time complexity. I'm sure there must be something better than this, however.

Answer 4

Graphical solution Each room is a node There are edges only between rooms where the door is open use the Floyd–Warshall algorithm and then to check the min distance between each room and each guard

number of rooms - R = N^2

number of guards - G

the time complexity is O(R^3 +R*G)= O(R^3) = O(N^6)

R^3 for Floyd–Warshall

Answer 5

I assume a function edgeCost(i,j) which returns the cost of the transition from room i to room j (infinite if there is none, 1 otherwise). Also edgeCost(i,i) = 0 and there are no negative cycles. Let R be the number of rooms (R = N^2 in your case):

int path[R][R];
/*
 * Each path[i][j] is initialized to
 * edgeCost(i,j) or infinity if there is no 
 * edge between i and j.
 */

function play():
 for k = 1 to R:
  for i = 1 to R:
   for j = 1 to R:
    path[i][j] = min(path[i][j], path[i][k] + path[k][j]);

Or as you may know it, the Floyd-Warshall algorithm (all pairs shortest paths), with O(|R|^3) time complexity.

Answer 6

If we augment the museum graph with an artificial source and zero-length edges from the source to each guard, then the single-source shortest paths tree, computable via BFS (unweighted)/Dijkstra (weighted) in time Õ(n² + g), gives the distance from each room to the nearest guard.

Answer 7

Have a queue whose entries each hold the address of one square along with an integer. Put the locations of all the guards in a queue, each tagged with the integer "0". Every square should have room for a number, and they should all be initially blank.

Then, as long as there's something in the queue, pull an entry out of a queue and check whether the square in question has a marked value. If so, just ignore that queue entry and proceed to the next one. Otherwise, mark the square with the value from the queue and put all directly-reachable neighboring squares in the queue with a value one higher than that of the present present entry (so as each of the first batch of squares is pulled from the queue, they'll get the value "1"). Each square will only be visited once when it's blank, and each visited square will result in at most four more squares being queued, so the total number of items going through the queue will be four times the number of squares, plus the number of guards. This value could easily be reduced by a constant factor by checking each square to see if it's blank before adding it to the queue; this would not eliminate all redundant queueing, but would eliminate some.

Answer 8

Here is a summary of the optimal solution (O(N^2)), mentioned by IVlad and throwawayacct. For some reason their voice is not heard :)

Consider the NxN grid as a graph with nodes representing rooms and edges representing doors between adjacent rooms. All edges have weight 1. A set of nodes U are marked as "guarded rooms".

The idea is to use a BFS traversal, that starts from a new node connected to all guarded rooms, and scans the rooms in increasing distance order from v0. Each time a node is visited, the number of steps that have been made for reaching it represents the distance from a guarded room, and it is guaranteed to be minimal due to the path expansion order:

Add an artificial node v0 and connect it to all nodes in U
Create a simple queue Q, that stores pairs <node, dist>
Q.enqueue(<v0, -1>) 
Create a hash set S, that contains all visited nodes
S.add(v0)
while not Q.isEmpty() {
    pathTail := Q.dequeue()
    output distance pathTail.dist for node pathTail.node
    for all neighbours v of pathTail.node
        if not S.contains(v)
            Q.add(<v, pathTail.dist + 1>)

    S.add(pathTail.node)

}

Complexity analysis

Note that the graph is planar, so we have |V|+|E|=O(|V|). Therefore, this BFS runs in O(|V|)=O(N^2) time.

The fact that we have a uniform weight for edges makes things simple; the queue is guaranteed to have monotonous distance values. With dijkstra for example, the edges can differ in their weight so a priority queue is needed, and this affects the time complexity. The same problem presented here, with varying weights between rooms would have required O(N*N*log N) time.