Can someone help me to think of a better way to adapt Dijkstra's Algorithm in these conditions? All I thought of so far wasn't good.
Example of input:
GP4578 MADRID 01:00 PORTO 02:00
IK6587 PORTO 03:00 VALENCIA 05:00 05:30 TENERIFE 08:00
AB5874 VALENCIA 05:40 BERLIM 10:00
"VALENCIA 05:00 05:30" This is a stopover, all of them are about 30min. The flight has arrival and departure time, flight number, the origin and destination city.
So, I need get the shortest path from a city to another, ok, no problem. I can't find how to structure this, I've been trying since last week. Can someone give me ideas? Which are my vertex's, each city or each flight? How to use the edges? How to do the stopovers?
Basically you can model it using each city/airport as a node and the flights as the connections in between. The weight of the connections/flights is then the time. If you assume that all stopovers are 30 minutes (in a simplified model) then you can add an additional cost per visited node (in this case 30 minutes)
Have a look at the picture on this Wikipedia page (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). Now check out this map with flights of busy airports http://www.worldmapsatlas.com/world-map/thematic/world-air-routes-map.html to get an idea how to build up the model.