CODEWITHSUNDEEP
algorithm
Cash Stramel
Cash Stramel

Reputation: 13

Shortest Distances To One Of Multiple Potential Destinations

I was asked on a programming test to solve a problem where I had to find the shortest distance from each node on a rectangular graph to one of a set of possible destinations on the graph. I was able to create a solution that passed all the tests but I'm fairly certain there is a more efficient algorithm out there.

C11--C12--C13--C14
 |    |    |    |
FGB--C22--C23--C24
 |    |    |    |
C31--C32--C33--C34
 |    |    |    |
C41--FGB--C43--C44
 |    |    |    |
C51--C52--C53--C54
 |    |    |    |
C61--C62--C63--FGB

So for example, on the graph above, say each "FGB" represents a Five Guys (because it's delicious). And each "Cxx" represents a customer. It was essentially, "How far is each customer from the nearest Five Guys?" So C11 is 1 away, C12 is 2 away, etc. All edges are weight=1.

Is Floyd-Warshall what I'm looking for? I don't really care about all pairs.

Any thoughts or reference materials you might point me to? Much appreciated.

Upvotes: 0

Views: 118

Answers (3)

Cash Stramel
Cash Stramel

Reputation: 13

In response to @yves-daoust (I know I'm not suppose to respond to other answers with a whole new answer, but this is too long for the "response to answer" dialog box).

So the whole thing would look something like this?

// O(n)
for each node:
  set node distance to infinity

// O(m)
for each FGB in FGB coordinate list
  directly set corresponding node distance to infinity

// O(n)  
for each i in row
  for each j in column
    if left and up exist
      set node(i,j) to min(node(i,j), left+1, up+1)
    else if left exists
      set node(i,j) to min(node(i,j), left+1)
    else if up exists
      set node(i,j) to min(node(i,j), up+1)

// O(n)
for each i in row (reverse)
  for each j in column (reverse)
    if right and down exist
      set node(i,j) to min(node(i,j), right+1, down+1)
    else if right exists
      set node(i,j) to min(node(i,j), right+1)
    else if down exists
      set node(i,j) to min(node(i,j), down+1)

The whole thing is O(3n+m) = O(n+m). Is that right?

Upvotes: 0

user1196549
user1196549

Reputation:

There's a simple solution that works in two passes.

The firt pass is forward, row by row. For every node, you evaluate incrementally the distance to the nearest target to the left of above.

D(node)= if target node => 0 else min(D(left neighbor) + 1, D(top neighbor) + 1)

The second pass is backward. The final distance is evaluated as

D(node)= min(D(node), D(right neighbor) + 1, D(bottom neighbor) + 1)

At the same time that you record a new value, you can record the location of the corresponding target.

(When a neighbor does not exist, the distance is infinite by convention.)

Upvotes: 2

trincot
trincot

Reputation: 351393

For an arbitrary graph size, with an arbitrary number of target nodes (FGBs), the following BFS algorithm will be the most efficient:

nodes = set of all nodes
currentNodes = set of target nodes (FGB)

for each node in nodes:
    dist[node] = infinity

for each node in currentNodes:
    dist[node] = 0

while currentNodes is not empty:
    newNodes := []
    for each node in currentNodes:
        for each neighbor of node:
            if dist[neighbor] > dist[node] + 1 then:
                dist[neighbor] := dist[node] + 1
                newNodes.add(neighbor)
    currentNodes := newNodes

The for each node loop will in total visit every node exactly once.

The for each neighbor loop will iterate at the most 4 times per node, given the graph is a rectangular one.

This means the inner if condition will be executed near 4n times, i.e. this is O(n). Depending on the used data structure the number can be 4n-4√n as the boundary nodes have fewer neighbors, but this is still O(n).

Note that if you have fewer than 4 target nodes (FGBs) it will be faster (though not significant in big-O terms) to use the rectangular properties of the graph to calculate the distances. You could do that with this formula, where m is the number of target nodes (FGBs):

dist[node at [i,j]] := min( abs(i-FGB[0].column)+abs(j-FGB[0].row),
                            abs(i-FGB[1].column)+abs(j-FGB[1].row),
                            ... 
                            abs(i-FGB[m-1].column)+abs(j-FGB[m-1].row)
                          )

This has a time complexity of O(n.m), which for a m limited to a certain constant still is O(n) and might be faster than the more generic solution.

An algorithm could make use of this, and depending on the value of m, could choose which method to apply.

Upvotes: 2

Related Questions