You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
114 lines
2.1 KiB
114 lines
2.1 KiB
How Not To Write a Flight Route Planner
|
|
|
|
1. Do not use real data
|
|
2. Do not use DFS
|
|
3. Do not use BFS
|
|
4. Do not use Dijkstra's (naively)
|
|
5. Lat/Lon are not coordinates
|
|
|
|
1. Do not use real data
|
|
|
|
Why?
|
|
|
|
- It is impossible to track down bugs,
|
|
especially when you get into a loop
|
|
that repeatedly prints:
|
|
[293, 23836, 202, 223, 2235]
|
|
- It can take a long time to load.
|
|
- It may be old data (it was)
|
|
|
|
2. Do not use DFS
|
|
|
|
Why?
|
|
|
|
- It may take a long time to complete
|
|
- It needs to check all possibilities
|
|
down possibly useless rabbit
|
|
holes before checking nearer paths
|
|
- It may find a long connection
|
|
before a short one
|
|
|
|
Consider the following
|
|
depth-first-search operations:
|
|
|
|
YYC -> YYZ
|
|
YYZ -> YVR
|
|
YYC -> YVR
|
|
|
|
3. Do not use BFS
|
|
|
|
Why?
|
|
|
|
- Does not take into account any weights:
|
|
- cost of flight
|
|
- distance of airports
|
|
|
|
Consider the following
|
|
breadth-first-search operations:
|
|
|
|
YYC -> AMS
|
|
YYC -> YVR
|
|
YYC -> YYZ
|
|
AMS -> TPE
|
|
YVR -> TPE
|
|
|
|
4. Do not use Dijkstra's (naively)
|
|
|
|
Why?
|
|
|
|
- What do you use for a weight?
|
|
- cost of flight
|
|
- number of connections
|
|
- distance between airports
|
|
- Selecting one of these,
|
|
without taking into account the others,
|
|
makes for a terrible flight planner
|
|
- You may want to have additional bounds
|
|
for example: you may want to confirm
|
|
that the schedule for the flight lines up
|
|
I could not find data for this, however
|
|
|
|
Q: What happens when you only take into
|
|
account the distance between airports?
|
|
A: A flight from YYC to TPE
|
|
would look like the following:
|
|
|
|
- YYC
|
|
- MSP
|
|
- GRR
|
|
- DTW
|
|
- EWR
|
|
- MAD
|
|
- CAI
|
|
- TUU
|
|
- DMM
|
|
- BAH
|
|
- DXB
|
|
- TPE
|
|
|
|
Q: Okay, so how do you implement a flight planner?
|
|
A: Use Dijkstra's, with multiple weights.
|
|
|
|
For mine, I used:
|
|
- The distance between airports
|
|
- + a fixed cost for connections
|
|
|
|
The distance could be swapped out with cost of flight.
|
|
I couldn't find a database of fare costs.
|
|
|
|
5. Lat/Lon are not coordinates
|
|
|
|
- You can not simply use (p1.lat - p2.lat).
|
|
- THIS WILL NOT WORK!
|
|
|
|
- Use a library, or learn a bunch of math.
|
|
- I used latlon3
|
|
|
|
Libraries:
|
|
|
|
- latlon3 (Python)
|
|
- nalgebra, nalgabra_sparse,
|
|
serde, rust_decimal (Rust)
|
|
|
|
Demo
|