It depends on when you do the query. Years ago (mid 2000s) at ITA, Carl wrote code to find the longest possible shortest route between any two airports with scheduled flights. At the time the winner was Wasu, New Guinea to Peawanuck, Ontario, which took a minimum of 90 hours and many flights. There are airports you can only get to at the end of a long line of stops; this drives the number of stops way up.
Back when airline status was based on number of segments this would have been a useful tool if you could find the lowest cost route on a single airline group. For example "find the most number of segments at the lowest cost per segment using only One World flights"
Make a connectedness matrix of airports x airports with 1 marking a connection and 0 marking no connection. You can now iterate over legs by multiplying the matrix with itself. Do this until all values in the matrix are zero. The previous iteration shows a 1 where the longest routes are.
Multiplying the adjacency matrix by itself gives the number of walks of a specified length. Therefore you would keep multiplying the matrix by itself until all values are nonzero. Then the previous iteration shows a zero where the longest routes are.
I don't know what this part of graph theory is called but I noticed in college that this is taught in the graph theory class from the mathematics department but not in the graph theory class from the computer science department.
My first thought was the Guam Island Hoper between Guam and Honolulu at 7 airports.
[added] 8 if you add MNL (Manila) on arrival to Guam
https://en.wikipedia.org/wiki/Island_Hopper
It depends on when you do the query. Years ago (mid 2000s) at ITA, Carl wrote code to find the longest possible shortest route between any two airports with scheduled flights. At the time the winner was Wasu, New Guinea to Peawanuck, Ontario, which took a minimum of 90 hours and many flights. There are airports you can only get to at the end of a long line of stops; this drives the number of stops way up.
ICAO four-letter airport codes are hierarchical. The first one or two letters indicate the country, e.g.:
EDDF - Frankfurt (E: Northern Europe, D: Germany)
EKCH - Copenhagen (E: Northern Europe, K: Denmark)
VTBS - Bangkok (V: South/Southeast Asia, T: Thailand)
KJFK - New York JFK (K: USA)
Using ICAO codes, you can make sense of a written out route at a glance. Taking one of the examples from the link:
AUY TAH VLI BNE BKK CPH SFJ JAV JUV NAQ
becomes
NVVA NVVW NVVV YBBN VTBS EKCH BGSF BGJN BGUK BGQQ
I.e.: Vanuatu (a few jumps) -> Australia -> Thailand -> Denmark -> Greenland (a few jumps).
Back when airline status was based on number of segments this would have been a useful tool if you could find the lowest cost route on a single airline group. For example "find the most number of segments at the lowest cost per segment using only One World flights"
Slightly unrelated, but you can book flights between Seattle (SEA) and Everett (PAE), and there's a PAE-LAS-SFO-SEA route that takes 20 hours.
These two Airports are only 37 miles away from each other. There's a shuttle between them that takes 75 minutes.
In a decade there will be a light rail that is even faster than the shuttle! (Between Everett and SeaTac or the city)
It looks like Alaska will sell you tickets for PAE to SEA via any one of SFO, LAS, LAX, PHX...
Yes, it's a popular 'mileage-run' route. Aka a flight routing that frequent flyers take solely for the purposes of gaining more miles/status
Make a connectedness matrix of airports x airports with 1 marking a connection and 0 marking no connection. You can now iterate over legs by multiplying the matrix with itself. Do this until all values in the matrix are zero. The previous iteration shows a 1 where the longest routes are.
Great idea but two typos.
Multiplying the adjacency matrix by itself gives the number of walks of a specified length. Therefore you would keep multiplying the matrix by itself until all values are nonzero. Then the previous iteration shows a zero where the longest routes are.
[dead]
What is this part of graph theory called, and are there similar insights from doing elementary operations on adjacency matrices?
I don't know what this part of graph theory is called but I noticed in college that this is taught in the graph theory class from the mathematics department but not in the graph theory class from the computer science department.