CODEWITHSUNDEEP
treematrixnodesunits-of-measurement
user188276
user188276

Reputation:

What is shortest distance between 2 nodes in a matrix?

I have a matrix 5x5 (25 nodes). Is there a formula that I can find the shortest distance between 2 node i and j in the matrix ?

Note: distance between 1 node and its neighbor is 1 unit.

=================

In my observation, there are many paths with the same distance between those 2 nodes i and j so i'm not sure if there is a formula to calculate the shortest one? I appreciate if anybody can help. Thanks.

Ex: 

* * * i *
* * * * *
* * * * *
* * * * *
* j * * *

Shortest distance between i and j is 6 units.

Upvotes: 0

Views: 960

Answers (3)

abcd
abcd

Reputation: 42235

I believe what you need is the L1 distance, also called the Manhattan distance. So if your two nodes have matrix indices (i1,j1) and (i2,j2), then the shortest distance between them is |i1-i2|+|j1-j2|.

This is of course, assuming you can't move diagonally.

Upvotes: 3

Jakub Konecki
Jakub Konecki

Reputation: 46008

Take a look at Metric Space

Upvotes: 0

Suroot
Suroot

Reputation: 4423

I would think that the normal Pythagorean theorem would work just fine. Get the X,Y difference between where you are and where you want to go; this will give you a negative or positive value. From this you should be able to move up/down left/right as needed until you are in the same row/column. Couldn't figure out how to get superscript; but this will work.

a^2 + b^2 = c^2

Upvotes: 0

Related Questions