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.
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.
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
Take a look at Metric Space
精彩评论