title: Python: A* routing from dataframe with longitude and latitude
body: <p>I have a dataframe with 30,000 records in the following format:</p>
  
  <pre><code>ID | Name | Latitude | Longitude | Country |
  1  | Hull | 53.744   | -0.3456   | GB      |
  </code></pre>
  
  <p>I would like to select one record to be the start location and one record to be the destination and return a path (list) for the shortest path. </p>
  
  <p>I am using Geopy to find the distance between points in km</p>
  
  <pre><code>import geopy.distance
  
  coords_1 = (52.2296756, 21.0122287)
  coords_2 = (52.406374, 16.9251681)
  
  print (geopy.distance.vincenty(coords_1, coords_2).km)
  </code></pre>
  
  <p>I have read how to do A* in python from the following tutorial:
  <a href="https://www.redblobgames.com/pathfinding/a-star/implementation.html" rel="nofollow noreferrer">https://www.redblobgames.com/pathfinding/a-star/implementation.html</a></p>
  
  <p>However they create a grid system to navigate through.</p>
  
  <p>This is a visual representation of the records in the dataframe:
  <a href="https://i.stack.imgur.com/4JJ2J.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4JJ2J.png" alt="enter image description here"></a></p>
  
  <p>This is the code I have so far however it fails to find a path:</p>
  
  <pre><code>def calcH(start, end):
      coords_1 = (df['latitude'][start], df['longitude'][start])
      coords_2 = (df['latitude'][end], df['longitude'][end])
      distance = (geopy.distance.vincenty(coords_1, coords_2)).km
      return distance
  </code></pre>
  
  <p>^Calculates the distance between points</p>
  
  <pre><code>def getneighbors(startlocation):
      neighborDF = pd.DataFrame(columns=['ID', 'Distance'])
      coords_1 = (df['latitude'][startlocation], df['longitude'][startlocation])
      for index, row in df.iterrows():
          coords_2 = (df['latitude'][index], df['longitude'][index])
          distance = round((geopy.distance.vincenty(coords_1, coords_2)).km,2)
          neighborDF.loc[len(neighborDF)] = [index, distance]
      neighborDF = neighborDF.sort_values(by=['Distance'])
      neighborDF = neighborDF.reset_index(drop=True)
  
      return neighborDF[1:5]
  </code></pre>
  
  <p>^Returns the 4 closest locations (ignoring itself)</p>
  
  <pre><code>openlist = pd.DataFrame(columns=['ID', 'F', 'G', 'H', 'parentID'])
  closedlist = pd.DataFrame(columns=['ID', 'F', 'G', 'H', 'parentID'])
  
  startIndex = 25479 # Hessle
  endIndex = 8262 # Leeds
  
  h = calcH(startIndex, endIndex)
  openlist.loc[len(openlist)] = [startIndex,h, 0, h, startIndex]
  
  while True:
  
  #sort the open list by F score
  openlist = openlist.sort_values(by=['F'])
  openlist = openlist.reset_index(drop=True)
  
  currentLocation = openlist.loc[0]
  closedlist.loc[len(closedlist)] = currentLocation
  openlist = openlist[openlist.ID != currentLocation.ID]
  
  if currentLocation.ID == endIndex:
      print("Complete")
      break
  
  adjacentLocations = getneighbors(currentLocation.ID)
  
  if(len(adjacentLocations) &lt; 1):
      print("No Neighbors: " + str(currentLocation.ID))
  else:
      print(str(len(adjacentLocations)))
  
  for index, row in adjacentLocations.iterrows():
      if adjacentLocations['ID'][index] in closedlist.values:
          continue
  
      if (adjacentLocations['ID'][index] in openlist.values) == False:
  
          g = currentLocation.G + calcH(currentLocation.ID, adjacentLocations['ID'][index])
          h = calcH(adjacentLocations['ID'][index], endIndex)
          f = g + h
          openlist.loc[len(openlist)] = [adjacentLocations['ID'][index], f, g, h, currentLocation.ID]
      else:
          adjacentLocationInDF = openlist.loc[openlist['ID'] == adjacentLocations['ID'][index]] #Get location from openlist
          g = currentLocation.G + calcH(currentLocation.ID, adjacentLocations['ID'][index])
          f = g + adjacentLocationInDF.H
          if float(f) &lt; float(adjacentLocationInDF.F):
              openlist = openlist[openlist.ID != currentLocation.ID]
              openlist.loc[len(openlist)] = [adjacentLocations['ID'][index], f, g, adjacentLocationInDF.H, currentLocation.ID]
  
  if (len(openlist)&lt; 1):
      print("No Path")
      break
  </code></pre>
  
  <p>Finds the path from the closed list:</p>
  
  <pre><code># return the path
  pathdf = pd.DataFrame(columns=['name', 'latitude', 'longitude', 'country'])
  def getParent(index):
  
      parentDF = closedlist.loc[closedlist['ID'] == index]
      pathdf.loc[len(pathdf)] = [df['name'][parentDF.ID.values[0]],df['latitude'][parentDF.ID.values[0]],df['longitude'][parentDF.ID.values[0]],df['country'][parentDF.ID.values[0]]]
      if index != startIndex:
          getParent(parentDF.parentID.values[0])
  
  getParent(closedlist['ID'][len(closedlist)-1])
  </code></pre>
  
  <p>Currently this implementation of A* isn't finding a complete path . Any suggestions?</p>
  
  <p>Edit:
  I have tried increasing the number of considered neighbors from 4 to 10 and I got a path but not a optimum path:</p>
  
  <p><a href="https://i.stack.imgur.com/JDnQ6.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/JDnQ6.png" alt="enter image description here"></a></p>
  
  <p>We are trying to get from Hessle to Leeds. </p>
  
  <p><a href="https://i.stack.imgur.com/GJG8v.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/GJG8v.png" alt="enter image description here"></a>
  ^ available nodes</p>
  
  <p>Raw Data:
  <a href="http://viridianforest.co.uk/data/stations.csv" rel="nofollow noreferrer">Link</a></p>