Interview: Find the Shortest Path to Multiple Elements

Question

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

Answer 1

As a start, consider a relatively naive approach.

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

If all minimum distances in a room should be known, BFS from each guard to each room.

It takes time G * (R+E) or something like G*(N*N+E) or G*(N*N) .

This, of course, can be optimized with memoization, as each BFS will re-process the subtrees that have already been completed. Depending on the configuration of the room, this can significantly reduce the G value compared to the above time complexity. I am sure there must be something better than this.

Answer 2

Graphic solution. Each room has a node. There are edges only between rooms where the door is open, use the Floyd-Warsall algorithm, and then check the minimum distance between each room and each security guard.

number of rooms - R = N ^ 2

number of guards - G

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

R ^ 3 for Floyd-Warsall

Answer 3

If we increase the museum graph with an artificial source and edges of zero length from the source to each defender, then the shortest-path tree with one source, calculated through BFS (unweighted) / Dijkstra (time-weighted) in time Õ (n ² + g) , gives the distance from each room to the nearest security guard.

Answer 4

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 the doors between adjacent rooms. All ribs have a weight of 1. A set of U nodes is designated as “guarded rooms”.

The idea is to use the BFS bypass, which starts with a new node connected to all protected rooms and scans the rooms in order of increasing distance from v0. Each time a node is visited, the number of steps that were taken to achieve it represents the distance from the guarded room, and it is guaranteed that it will be minimal due to the order of the extension of the path:

 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) } 

Difficulty analysis

Note that the graph is flat; therefore, we have | V | + | E | = O (| V |). Therefore, this BFS works in O (| V |) = O (N ^ 2) time.

The fact that we have a single weight for the ribs makes things simple; A uniform distance value is guaranteed in the queue. For example, using dijkstra, the edges can differ in their weight, so a priority queue is necessary, and this affects the time complexity. The same problem presented here, with different weights between rooms, would require O (NNlog N) time.

Answer 5

You just need to look at this museum as one graph and use the Digikstra algorithm.

wiki link

You have a discussion of complexity on this page.

Answer 6

You can find the Dijkstra shortest path algorithm implemented in this series of messages:

Preliminary search in width and depth

Answer 7

I assume the function edgeCost (i, j), which returns the cost of switching from room i to room j (infinite if it is not, 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, the Floyd-Warsall algorithm (all pairs of shortest paths) with time complexity O (| R | ^ 3).

Answer 8

There is a queue whose records contain the address of one square along with an integer. Place the places of all the guards in the queue, each of which is marked with the integer "0". Each square must have a number for the number, and all of them must be initially empty.

Then, while something is in the queue, pull the record out of the queue and check if the square in question has a value with the marked value. If so, just ignore this entry in the queue and move on to the next one. Otherwise, mark the square with the value from the queue and put all neighboring squares with direct accessibility into the queue with a value greater than the value of the current real record (since each of the first batch of squares is pulled out of the queue, they will get the value "1"). Each square will be visited only once when it is empty, and each visited square will result in no more than four squares being queued, so the total number of elements passing through the queue will be four times the number of squares, and the number of guards. This value can easily be reduced by using a constant coefficient by checking each square to see if it is empty before adding it to the queue; this will not eliminate all redundant queues, but eliminate some of them.