c++ - 首先从 A 点通过最近邻点到达所有剩余点

Question

我在图片中表示了多个点。两个最近点之间的垂直距离(A 和 B 之间，或 B 和 C 之间，或 D 和 E 等之间)是 distance_y .两个最近点之间的水平距离(在 A 和 D 之间，等等)是 distance_x .

假设:

distance_y < distance_x < 2*distance_y

                distance_x
           A <-------------> D <-------------> G
           | 
distance_y |
           | 
           B <-------------> E <-------------> H

           -

           C <-------------> F <-------------> I

我将任意两点之间的距离公式化如下:

Distance(point P1, point P2) = m * distance_x + n * distance_y 

例如，对于点A和 B , m = 0和 n = 1;

问题是:从一个点P , 我怎样才能首先通过最近的邻居遍历所有剩余的点(即按照离点 P 的距离的降序排列)？

我不想计算从其他点到 P 的整个距离然后按照与 P 的距离降序对这些点进行排序因为这很耗时。我想搜索可以快速评估邻居位置而无需计算其他点位置的算法。

例如，从点 D , 将有以下几点

E (m= 0, n = 1),
A (m= 1, n = 0),
G (m= 1, n = 0),
F (m =0, n = 2),
B (m= 1, n = 1),
H (m= 1, n = 1),
C (m= 1, n = 2),
I (m= 1, n = 2).

如何确定 m 的顺序和 n搜索最近的邻居？

Answer 1

不确定我是否理解，但看起来像 Dijkstra 算法应用程序: http://en.wikipedia.org/wiki/Dijkstras_algorithm