The A* algorithm, applied to finding airports routes with a given maximum leg distance.

airports.rb

# About:
# A flight planning algorithm, particularly useful for private pilots.
# The idea is that one might be interested in, say, flying into LED (in Russia)
# from DCA (in DC); bearing in mind that small aircraft can only go so far
# on a single tank of gas, this algorithm will perform the hard work of
# computing a rather tricky route.
#
# Concretely:
# Given a set of airports (and their code, latitude and longitude),
# find the shortest route between any given airport A and B,
# where any given leg is <= N miles.
#
# For the curious, this is, more or less, an implementation of A*.

require 'csv'
require 'algorithms'
require 'faster_haversine'

# The airport data structure.
class Airport
  # The properties of an airport.
  attr_accessor :code, :name, :lat, :lon, :elevation

  # Returns an array of all the airports from a given CSV.
  def self.from_csv(path)
    # Keep CSV from complaining about illegal quotes.
    options = {quote_char: '$'}

    airports = CSV.read(path, options)
    airports.map! do |array|
      airport           = Airport.new
      airport.code      = array[0]
      airport.name      = array[1]

      # Radians to degrees
      airport.lat       = array[2].to_f * 57.29577951308232
      airport.lon       = array[3].to_f * 57.29577951308232

      airport.elevation = array[4]

      airport
    end

    airports
  end

  # Calculates the Haversine distance between this airport and the one given.
  def distance_to(airport)
    kilos = FasterHaversine.distance(self.lat, self.lon, airport.lat, airport.lon)
    kilos / 1.609344
  end
end

# A simple undirected graph.
class Graph
  def initialize
    @graph = {}
  end

  # Gets all adjacent nodes of a given node.
  def [](node)
    @graph[node]
  end

  # Adds an edge to the graph, consisting of nodes a and b.
  def add_edge(a, b)
    (@graph[a] ||= []) << b
    (@graph[b] ||= []) << a
    self
  end

  # All nodes within the graph.
  def nodes
    @graph.keys
  end
end



# The furthest distance that we think someone might query for.
# When we create the graph, we will only connect nodes (airports)
# that are within this distance.
max_distance = 700

# Load up the airports from the CSV.
airports = Airport.from_csv("airports.csv")

# Obtain all combinations of size 2.
combinations = airports.combination(2)

# Populate the graph.
graph = Graph.new
combinations.each do |a, b|
  graph.add_edge(a, b) if a.distance_to(b) <= max_distance
end

# This is the A* algorithm.
# `start' and `goal' can either be an instance of Airport,
# or the airport code as a string.
def find_path(graph, start, goal, max_distance)
  start = graph.nodes.find {|a| a.code == start} if start.is_a?(String)
  goal  = graph.nodes.find {|a| a.code == goal}  if goal.is_a?(String)

  visited = {}
  queue = Containers::PriorityQueue.new
  queue.push([start, [], 1], 1)
  until queue.empty?
    spot, path_so_far, cost_so_far = queue.pop
    next if visited[spot]
    visited[spot] = true
    newpath = path_so_far + [spot]

    return newpath if spot == goal

    graph[spot].each do |newspot|
      next if visited[newspot]
      distance_to_newspot = spot.distance_to(newspot)
      if distance_to_newspot <= max_distance
        newcost = cost_so_far + distance_to_newspot
        priority = -1 * (newcost + newspot.distance_to(goal))
        queue.push([newspot, newpath, newcost], priority)
      end
    end
  end

  nil
end

# Given a graph of all airports,
# find the shortest route between DFW and BWI,
# where any given leg is <= 100 miles.
path = find_path(graph, "DFW", "BWI", 100)
puts path.map(&:code).join(", ")

# Output:
# DFW, 46TS, XS30, DEQ, 4AR6, RBM, 4AR5, 93AR, HZD, 36TN, 4KY1, 53KY, JKL, K22, WV01, WV52, 9VA4, 98VA, BWI

What an amazing gist.