1
$\begingroup$

I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in a certain scope/range. However when expanding this to an infinite 2D grid, I don't understand when (say using BFS as an example) to conclude that a path simple doesn't exist without having the algorithm run infinitely since I can't use grid size as a boundary condition. Is there some kind of formula that can be used in these cases? Also, take into account that there could be obstacles along the path too so the path distance can vary from different origins to destinations.

I've considered trying to take the absolute value of the difference between the coordinate points and raising it to some power as a way of setting an upper limit of steps taken before considering that a path must not exist, but this approach is obviously lacking and incorrect to say it bluntly since it doesn't work for many cases.

I apologize if my question is confusing. I'll restate it here: basically, how do I know when to assume a path from an origin to a destination doesn't exist in an infinite 2D grid?

$\endgroup$
  • $\begingroup$ How is the infinite 2D grid given? If there is a finite number of obstacles, sure you can only consider the finite part of the board, which is their (plus start point and end point) bounding rectangle, expanded a little. If the number of obstacles is infinite, there's no general-case recipe, but it may still be possible to deduce the existence of the path from the obstacles' structure. $\endgroup$ – Gassa Jun 18 '18 at 21:40
  • $\begingroup$ The start and end point are known but the grid itself isn't given, so I've decided to pursue a bfs approach to find a path. Assuming there are a finite number of obstacles, I'm confused on how to calculate the bounding rectangle and how much extra space to allow to make certain a path either exists or doesn't. $\endgroup$ – TheDifficultyOfAlgortihms Jun 18 '18 at 22:00
  • $\begingroup$ What properties does the grid have? Does each cell have a (possibly different) cost associated with moving through it? If not, one cell of extra space will be sufficient. $\endgroup$ – Gassa Jun 18 '18 at 22:12
1
$\begingroup$

Unfortunately, the simple answer is, you can't.

All the standard search algorithms have a runtime that's polynomial in the size of the graph. If your graph is infinitely large, there's no guarantee that they'll ever terminate for arbitrary inputs: how can they ever know whether they should give up now, or whether they'd find the answer if they just expanded one more node?

Any approach that involves putting an upper limit on the number of steps, is doomed to failure. Even if the start and end points are right next to each other in the coordinate system, I could delete the edge between them, then make it so that the shortest path from one to the other takes one more step than you're allowing. And then your algorithm will say, incorrectly, that there's no solution.

However, if you have additional information about your graph (perhaps there's only a finite number of edges missing from the grid?), then you can potentially exploit this to find an answer. It's only impossible for arbitrary infinite graphs; there are many classes of infinite graphs for which it can be solved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.