Flying Short Distance With Ruby And Dijkstra

It’s been long since I wrote a decent program in Ruby; decent as in non-trivial, non-Hello-World program, but not one for a client to put in production. I find Ruby coding a pleasure because of its support for ‘Perl-isms’.

The program I wrote is to find the shortest distance between two airports. If we setup the airport IATA codes as vertices of a graph, and distance between two airports as the edge weight between two vertices, Dijkstra’s Algorithm will find the shortest path between two given airports.

The website openflights.org on its data page, gives a data file (airports.dat) that we can download. It’s a file with comma separated values. The fifth value on each line is the airport IATA code. The seventh and eighth fields are the latitude and longitude of that airport.

If we know the latitude and longitude of two airports, we can find the great circle distance between them using the Haversine formula. From Wikipedia : “The haversine formula is an equation important in navigation, giving great-circle distances between two points on a sphere from their longitudes and latitudes.” A sample implementation of the Haversine formula, in JavaScript, is available on this --> page.

Now, the same site, openflights.org also gives a data file “routes.dat”, which is also a comma-separated values file. The third value is the “from” airport (orig), and the fifth value is the “to” airport (dest). Basically it gives the airline connections, but not the distances.

So, we take each air connection’s orig and dest airports from routes.dat, fetch the two airports' latitude and longitude from airports.dat, calculate the distance for that air connection, and construct the graph edge. Once we have the graph, we take the orig and dest from the user, and invoke the djikstra method on the graph to find the shortest flight distance between the two airports.

Luckily I didn’t have to write Djikstra’s algorithm in Ruby. There are quite a few examples available on the net. I took the one by Tony Lee (github user roganartu) and called it from my program. To summarize, here’s the programming logic:

• Open airports.dat
• On each line, airport IATA code = 5th value, latitude = 7th value, longitude = 8th value
• Populate airport IATA code, latitude, longitude in a data structure (hash, key=code, value=list[latitude, longitude]
• Take one Ruby implementation of Dijkstra’s Algorithm (RDA), initialise a graph.
• Open routes.dat
• On each line, orig airport IATA code = 3rd value, dest airport IATA code = 5th value
• Make Graph vertices from the IATA codes (if they are already not vertices)
• Calculate distance :
• —- Get orig airport latitude & longitude, dest airport latitude & longitude
• —— and pass them to haversine method to get distance
• Connect the airports with distance as graph Edges
• Take an airports pair as user input
• Call dijkstra method passing the two airport codes and print the shortest path and distance

The code is:
Note: if you want to actually run my program, please make sure you have the files airports.dat, routes.dat and dijkstra.rb in the same directory. Remove lines 107 - 122 from dijkstra.rb. Given below is a sample run.

mh-iMac:Ruby mahboob$ ./airport-distances.rb
"Enter from-city"
DEL
"Enter to-city"
WIN
{:path=>["DEL", "SIN", "DRW", "TSV", "WIN"], :distance=>9873}

Some time in the next few days, I will try to do some timing runs.