tree - 矩阵中两个节点之间的最短距离是多少？

Question

我有一个 5x5（25 个节点）的矩阵。是否有一个公式可以找到矩阵中 2 个节点 i 和 j 之间的最短距离？

注意：1 个节点与其邻居之间的距离为 1 个单位。

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

在我的观察中，这两个节点 i 和 j 之间有许多距离相同的路径，所以我不确定是否有计算最短路径的公式？如果有人可以提供帮助，我将不胜感激。谢谢。

前任：

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

i 和 j 之间的最短距离是 6 个单位。

score 3 · Accepted Answer

我相信您需要的是L1距离，也称为曼哈顿距离。因此，如果您的两个节点具有矩阵索引(i1,j1)和(i2,j2)，那么它们之间的最短距离是|i1-i2|+|j1-j2|。

当然，这是假设您不能沿对角线移动。

score 0 · Accepted Answer

我认为正常的勾股定理可以正常工作。获取您所在位置和您想去的位置之间的 X、Y 差异；这会给你一个负值或正值。从这里你应该能够根据需要向上/向下左/右移动，直到你在同一行/列中。无法弄清楚如何获得上标；但这会起作用。

a^2 + b^2 = c^2

score 0 · Accepted Answer

0

于 2011-03-27T00:29:06.390 回答

3 回答 3