Minimum cost path from (0,0) to (N,N) on 2D grid

Question

I have a problem with a 2D grid, where you are trying to find the shortest path from (0, 0) to (N, N), where 1 < N < 10^9. There are also P (1 < P < 10^5) shortcuts, where you can jump from (x1, y1) to (x2, y2).

When you travel, you can only walk up or to the right. Similarly the shortcuts will never move you down or to the left.

Sample case: You are at (0, 0) and are trying to reach (3, 3). There are two shortcuts: one moves you from (0, 1) to (0, 2), and one moves you from (1, 2) to (2, 3).

The best path is:

Move from (0,0) to (0,1) (1 unit). Shortcut to (0,2). Move from (0,2) to (1,2) (1 unit). Shortcut to (2,3). Move from (2,3) to (3,3) (1 unit).

So the total length would be 3 units.

The time frame is also 2 seconds.

EDIT 1: I had the idea to use dynamic programming, to do a cost matrix. The matrix[i][j] = total cost of path to reach (i, j). However, the grid is huge and the matrix would have 10^18 slots, which is too large and wouldn't fit in the time frame.

EDIT 2: The next idea I had was to use Dijkstra's algorithm; simply make the end, the start, and the shortcuts all nodes in a graph. However, this becomes an O(N^2) solution (there are at most 10^10 edges!)

EDIT 3: I came up with another O(N^2) solution. Basically you would sort all the shortcuts based on their distance from their origin. Then, you would find the shortest path to each shortcut, by iterating through all the shortcuts you processed already. You would find the minimum of (distTo(each shortcut) + manhattan_distance(each_shortcut, current shortcut)). At the end, you would process the (N, N) point as if it was a shortcut to find your final solution.

However, this is still too slow - is there a way to optimize my solution further or a better one?

Answer 1

Let's notice that we can count distance from point A to point B in const time abs(a.x - b.x) + abs(a.y - b.y). We can sort all points by its coordination. After we would to run something like dp -> dist for point x will be the minimum dist scores from portals with i.x <= x.x && i.y <= x.x where i is an exit from portal, + dist from exit to point x. (consider only x if it is entrance or end of the array). We need to also remove previously considered points and replace it with a new "virtual" point with the best score if the point has worst score in coordinates on x coordinate if we considering x as our second for loop.

Answer 2

Do you have to find absolutely the best solution, or just a very good one? In most CS problems in the real world, finding a very good solution quickly is better than finding the absolutely best one slowly.

Assuming that a very good solution quickly is preferable, this would be my approach:

Sort the shortcuts according to how good they are: i.e. the Manhattan distance that they save you.

For the top M shortcuts, where M is a small fraction (1/100, perhaps, or even 1/1000) of the available shortcuts, you're going to calculate a "very good" path that uses that shortcut. Then just pick the best of those paths.

For each of the shortcuts you're testing, use recursion to find a "very good" path for the rectangle defined by start to its entrance, and and the one defined by its exit to the end. Since you have already sorted the shortcuts, now you are finding the top M shortcuts that are within a smaller rectangles. Count those as you go through them, so that you are, again, using the top small fraction of them.

Within the structure for each shortcut you save, once you have it, the distance to its start and the distance from its end to the end of the full matrix. This will allow a fair bit of pruning.

Once you finish the recursion and choose a best path, you have to repeat the recursion to be able to say what that path was, but every step will be pre-pruned so it will actually be a very thin "tree" (in quotes because it doesn't ever branch).