1
$\begingroup$

I have an $n$-dimensional grid space with two points on it defined by ordered pairs. I want to find the shortest path between the two points, but I can only increase one number in the ordered pair at a time. Is there an algorithm for this or at least one I can refer to?

$\endgroup$
  • 2
    $\begingroup$ Can you clarify: (a) what's a grid space? (b) By ordered pair, do you mean $n$-tuple? $\endgroup$ – usul Feb 28 '13 at 0:05
  • 4
    $\begingroup$ This is not a research-level question. The shortest path from (a,b) to (c,d) walks east c-a steps and then walks north d-b steps. $\endgroup$ – JeffE Feb 28 '13 at 0:54
3
$\begingroup$

It's easy: first get the 1st dimension right, then the 2nd dimension, then the 3rd dimension, etc.

For example, if you want to get from $(1,3,0)$ to $(3,4,1)$, you go via the following sequence of points: $(1,3,0), (2,3,0), (3,3,0), (3,4,0), (3,4,1)$.

$\endgroup$
1
$\begingroup$

Take a look at Floyd's algorithm. I would also suggest reading up on how to permute co-ordinates to generate Hamiltonian paths through n-dimensional space. Gray codes mutate one bit at a time and are related to the problem you state. As an aside, I don't understand how you can define a point in n-dimensional space with just a pair of co-ordinates, unless n=2.

$\endgroup$
0
$\begingroup$

Its the best you can do. Because its the minimum distance.

Its like driving taxicab in n-dimensional space.

$$d(P,Q) = \sum\limits_{i = 1}^{n} | P_i - Q_i|$$

P and Q are points in n-dimensional space and $P_i$ is gives $i^{th}$ co-ordinate of P.

It will take time linear in the distance between P and Q which is $d(P,Q)$.

$\endgroup$

Your Answer

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