0

I have this problem that I am working on that has to do with the greedy best first search algorithm. However I am bit stuck on computing the length of the traverse when it comes to points (x, y). For example lets say I have these points: (0, 1), (0, 2), (1, 2), (1, 3). So what I did is draw out a diagram on the x, y plane: Diagram

Now knowing the GBF algorithm, it goes to check the closet node and so in this case the transverse would look like so: (0, 1)->(0, 2)->(1, 2)->(1, 3). So now in order to compute the length of the points connections done by the GBF, do I need to basically add up the path, which in this case would be three? Any clarifications would be helpful.

KonoDDa
  • 41
  • 5

1 Answers1

0

The first part is to find the best way to store the graph using appropriate data structure.

Say the graph looks like this now. 

         (1,3)P4
           |
P2(0,2)--(1,2)P3
  |
(0,1)P1
  |
(0,0)P0

One way to represent this graph would using Adjacency List. Like this

P0 => P1
P1 => P2
P2 => P3
P3 => P4

Now using Breath first Search the distance between two points can be calculated in linear time. The distance between two nodes(points) with the path length being the number edges.

Explanation for BFS can be found here

thebenman
  • 1,621
  • 14
  • 35