Search code examples
algorithmpath-finding

Pathfinding with waypoints in any order

  • I have a list of waypoints(list of 2d-points) in a 2d-area.

  • I want the shortest path to visit any waypoint at least one time.

  • The order of visiting does not matter

Do I have to bruteforce that?

  • Calculate distances between all points
  • Walk through any path.
  • return the shortest
Solution

  • Your problem is a variant of Hamiltonian Path / Traveling Salesman Problem.

    These problem are NP-Complete, but if the number of "waypoints" is relatively small, you can brute-force your way to solve it, after some preprocessing is done.

    First, create a new graph:

    G'=(V',E', w') Where
V' = {v | v is a waypoint }
E' = { (u,v) for all u,v in V' }
w'(u,v) = D(u,v) (where D is a function for shortest path between waypoints in the original graph) (D:VxV->R)

    You can create w' by using an all to all shortest path algorithm, such as Floyd-Warshall. This is done in O(|V|^3).

    After you have it, run a brute force (O(n!), where n is the number of waypoints) or Dynamic Programming (O(2^n*n)), to solve the Traveling Salesman Problem you have.