The other day, I attempted to plan an itinerary for my upcoming trip to London. Sadly, there were no direct flights to London from Cebu, Philippines.
As I was brainstorming on how to plan my flight such that I would incur the minimum cost, I remembered that I had access to the “secret” discounted airfare database of an Alliance of at least 30 airliners. I downloaded the entire database and made an adjacency matrix of destinations per airline and their corresponding costs.
The adjacency matrix was 913×913 big, but Java was good enough to handle it. I then coded the Floyd-Warshall algrorithm to find the shortest path slash minimum cost. I had to keep a predecessor list so that I can retrace the path.
Floyd-Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted, directed graph. A single execution of the algorithm will find the shortest paths between all pairs of vertices. -Wikipedia
After retracing the path, I learned that it will take me at least 42 hours to finish the flight since most of them were not connecting flights. I tried to rerun the program in such a way it would make use of connecting flights and flight time was reduced to 17 hours.
In the end, I still preferred the 42 hours trip since it was 40% cheaper than the other.
Back in college, I thought that Floyd-Warshall algorithm wasn’t that useful. But it actually was. 
Post a Comment