I saw few similar problems on this forum, but they didn't match exactly what I need. The problem is: given a file with names of cities, their latitudes and longitudes, a program must calculate distance between them. But, it isn't all. A program must create a database of all this cities and user specifies which cities are connected with an airline (flight). Then, user can create queries about distances between certain cities, connected with direct flight, or indirect (in which case program must select shortest connection). In the end, program must be able to find shortest roundtrip for given set of cities.
set_flights option [filename], where option can be file, random, all, none
add_flight source destination
remove_flight source destination
get_flight from | * to | *
shortest_connection from | * to | *
shortest_roundtrip a1 . . . an | all
I'll give an example what program should do.
ZAG 45.73458 16.06295
BRU 50.901702 4.483025
LHR 51.469883 -0.448144
PRG 50.101607 14.256674
TLL 59.416521 24.799303
remove_flight ZAG TLL
get_flight ZAG *
ZAG -> BRU : 1029.34 km
ZAG -> LHR : 1369.11 km
ZAG -> PRG : 503.86 km
shortest_connection * TLL
BRU -> PRG -> TLL : 1930.3 km
LHR -> TLL : 1805.29 km
PRG -> TLL : 1233.88 km
ZAG -> PRG -> TLL : 1737.74 km
ZAG -> BRU -> LHR -> TLL -> PRG -> ZAG : 4921.74 km
Still here?? OK, I haven't even started yet because I can't decide how to design classes to support this operations. Because I have no experience in designing classes, a few advices about class design would be highly appreciated. Professor suggested us to use object oriented principles, as well as templates.
This problem is about graph theory and can be easily modeled in mathematics. Locations are nodes, and flights are weights. Dijkstra algorithm can be used to find a trip of lowest cost, and haversine formula to calculate distances...
But I need help in designing classes. Implementation will be easier because I have some experience in programming (but not object oriented programming), and theoretical knowledge in C++.
Any help would be appreciated.
P.S. Sorry for my bad english.