Finding the shortest distance on a grid

[TheGosuStandard]

Hello, I am looking for a way to find the shortest distance (closest point) from a current location to that of a target location which is found within a vector using structs as x & y coordinates.  Currently I start at a certain point on the grid and travel to the next vector point until I have iterated through the vector, however since the points in the vector can be mixed up and all over the place on the grid it takes up a lot of time. 

 

I'm not sure how well I explained the problem, so if you need further explanation let me know and I'll try my best to.

[Mr_KoKa]

I think that path finding is what you are looking for, and algorithms like A* (A star) or Dijkstra. A* is Faster Dijkstra is more precise.

[fizzlesticks]

Is this for the advent problem?

If so, the shortest path would be to walk horizontally until your X matches the target X then vertically until your Y matches the target Y. So the total distance would just be horizontal distance + vertical distance.

 

[TheGosuStandard]

5 minutes ago, Mr_KoKa said:

I think that path finding is what you are looking for, and algorithms like A* (A star) or Dijkstra. A* is Faster Dijkstra is more precise.

Thanks, I'll take a look into this. 

4 minutes ago, fizzlesticks said:

Is this for the advent problem?

If so, the shortest path would be to walk horizontally until your X matches the target X then vertically until your Y matches the target Y. So the total distance would just be horizontal distance + vertical distance.

 

What advent problem?

 

Wouldn't walking horizontally until you match X and then Y not take into account all the points in the vector (x,y). I feel as if I need to compare the current location to all the points in the vector to find the closest one and go on from there continuously comparing to find the shortest. 

[fizzlesticks]

2 minutes ago, TheGosuStandard said:

What advent problem?

2016 Advent of code started today and the first problem is about shortest paths on a grid, just a coincidence I guess, ignore my answer.

[dannytech357]

2 minutes ago, TheGosuStandard said:

Thanks, I'll take a look into this. 

What advent problem?

 

Wouldn't walking horizontally until you match X and then Y not take into account all the points in the vector (x,y). I feel as if I need to compare the current location to all the points in the vector to find the closest one and go on from there continuously comparing to find the shortest. 

The advent he's referring to is the first challenge in the Advent of Code.

[TheGosuStandard]

2 hours ago, Mr_KoKa said:

I think that path finding is what you are looking for, and algorithms like A* (A star) or Dijkstra. A* is Faster Dijkstra is more precise.

 

After looking over Dijkstra algorithm I seem to be confused in terms of applying it. Aside from that I know some people that are using euclidean's distance formula for comparison of the initial target to the rest of the vector. 

[Nineshadow]

So you want the shortest path from one point to another in a graph? Tons of ways of doing it.

 

Use a greedy approach with Djisktra's algorithm or a more heuristic one with A*. Dynamic programming with Bellman-Ford or Roy-Floyd (although Roy-Floyd computes the shortest distances between each pair of nodes in the graph). Look them up on Google.