Constructing a graph path using a best first strategy

Question

I want my program to construct a path using a best first(greedy) strategy (i.e the next point picked to be in the path will be the one closest to the current point), from a given list of lists of distances, where distances[i][j] is the distance between point i to point j.

I have an issue in a fragment of my code which is responsible for finding the lowest dist:

        for i in range(len(pointsLeft) - 1):
            if i in pointsLeft and i not in path: #only looks at points still not in path
                lowDist = distances[lastPoint][i]
                nextDist = distances[lastPoint][i + 1]
                if nextDist < lowDist:
                    lowDist = nextDist

I noticed that for the first few loops the code works correctly, but then it finds the wrong min value.

score 0 · Accepted Answer · answered Mar 23 '20 at 14:19

You have to reinitialize lowDist to an arbitrarily high value or else you might preserve former values of lowDist that you don't want. Furthermore, you check only nodes labeled from [0, len(pointsLeft)-1), rather than the specific nodes remaining, and instead you want something like

lowDist = 100000000  # just set this value to anything greater than all the edges
for i in pointsLeft:
     nextDist = distances[lastPoint][i]
     if nextDist < lowDist:
          lowDist = nextDist

Which checks all and only the nodes in pointsLeft. Also notice that any node in pointsLeft will automatically not already be in the path, so you don't need to check that separately.

Constructing a graph path using a best first strategy

1 Answers1