Domino path algorithm

2015-03-04

An answer to this question on Stack Overflow.

Question

I've got some (I hope) easy question about algorithm that can resolve the "domino path" problem. I'm looking for resolution that will resolved this problem in less then O(n^2) complexity.

I've got a group of n-points (n in [1,100 000], every point is diffrent) with x and y coords: (0,1) (1,3) (1,2) (2,4) (3,5) (4,2) (5,0)

I'm looking for the "path" from start point (0,y) to the end point (x,0) (the other point need to be sticked like domino block). In this example the path will be looking like this: (0,1) > (1,3) > (3,5) > (5,0). If the points will create more than one path - choose any of them. Could it be done is less than O(n^2)?

EDIT: Thanks for graph algorithm, but can it be done without it? I'm looking for some tricky recurrence algorith or something like this.

Answer

Yes. You should read up on Dijkstra's algorithm which runs in O(E+V log V) where E is the number of edges in your graph and V is the number of vertices. A breadth-first search would also work, since the graph is unweighted. That would run in O(E+V) time.

Though these are common ways of solving this problem, they are by no means the only ones.