开发者

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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜