Optimized wayfinder

Question

I have a quite difficult problem to solve and I'll try my best to describe it. I'm not a native English speaker so if there is any doubt about what I meant, ask me

Description

I'm struggling with some sort of pathfinder. I have a grid with a list of N points of coordinates [x,y]. You need to go from a point A to a point B, both belonging to the previous list. You can only move between two existent points. I need a function which takes as parameters the list of points, the start point A, the end point B and a maximum distance D.

The goal is to find whether you can go from A to B using intermediate points without having to ever travel more than a distance D between two consecutive points of your path. In case you can't, we need to find the minimal distance D' which follow the rule above.

---

An example:

To go from point 7 to point 5 on this graph, the path that minimize the maximum distance ever traveled between two points is 7 > 1 > 17 > 15 > 8 > 10 > 3 > 16 > 5

---

Solution

I've come up with a solution to this problem using Python. However, when there are more than a hundred points, my script is suffering. I've really tried to optimize this to the maximum by reducing useless memory affectation and trying to avoid useless tests, however, it's still not sufficient. Do you have any ideas on how to improve it's effectiveness? I've thought to try recursive methods but I don't think this will change anything since this is just an iterative way to write recursion. Any tips is welcome :)

My solution to the problem using python:

def OptimizedPath( a, b, points, Dmax ):
# Dmax is the maximal distance you can travel between two points
# D is a function which calculate the distance between two points
maxi = D( points[a], points[b])
if maxi < Dmax: # if the direct travel is already ok
    return Dmax
else:
    ways = [[a]]    # itervative methode to explore all paths
    while ways != []:
        nways = []  # new matrix that will contain all paths of n+1 points
        for w in ways:
            # PAcc returns the list of points you can access in less than a distance maxi
            for i in PAcc( w, maxi, points):
                nways.append( w + [i] )

        ways = []
        for w in nways:
            if w[-1] == b:  # if a path has arrived to it's destination
                if Dmaxw( w, points ) < Dmax:   # if it has done it without traveling more than Dmax between two points
                    return Dmax
                elif Dmaxw( w, points ) < maxi: # if it has done it better than the best path found
                    maxi = Dmaxw( w, points )
            elif Dmaxw( w, points ) < maxi: # if it's not over and the maximum distance between two points is smaller than maxi
                ways.append( w )
    return maxi

Answer 1

Treat your grid like a Graph, each point as a vertex. Find distance between each pair of vertices and then you can find minimum distance between point A to B using Dijkstra Algorithm (single source shortest path algorithm). Though the time complexity will remain O(n^2) as you need to find distance between each pair of vertices initially.

Answer 2

Allright folks,

I want to give a huge thanks to you all, but in the end the Dijkstra algorithm solved everything. I had trouble adapting it to this specific problem since this was my first time with those advanced graph optimization algorithm and I didn't wanted to find the shortest way but the maximal distance between two points. It finally worked and brought way better result (both in time and memory usage).

The solution to my problem, using python

def nextc( A, U ):
    mini = A[U[0]][0]
    indice = U[0]
    for i in range(1,len(A)):
        if A[i][0] < mini and i in U:
            mini = A[i][0]
            indice = i
    return indice

def DijkstraS( s, e, points ):
    L = D( points[s], points[e] )
    U = [ x for x in range( len(points) ) ]
    A = [ [float('inf'), -1] for i in range(len(points))]
    A[s][0] = 0
    while U != []:
        current = nextc( A, U )
        U.remove(current)
        for P in U:
            Dt = D( points[P], points[current] )
            if Dt < L and max( Dt, A[current][0]) < A[P][0]:
                A[P][0] = max( Dt, A[current][0])
                A[P][1] = current
    return A[e][0]