{"id":165,"date":"2020-12-28T10:02:46","date_gmt":"2020-12-28T10:02:46","guid":{"rendered":"https:\/\/awan.com.np\/?p=165"},"modified":"2023-02-23T10:30:24","modified_gmt":"2023-02-23T10:30:24","slug":"flight-scheduling-agenda-problem-using-dijkstras-algorithm-with-python-code","status":"publish","type":"post","link":"https:\/\/awan.com.np\/flight-scheduling-agenda-problem-using-dijkstras-algorithm-with-python-code\/","title":{"rendered":"Airline Flight Agenda Scheduling Problem using Dijkstra\u2019s Algorithm"},"content":{"rendered":"\n

For our Algorithm and Complexity Course here at Kathmandu University, I was given this mini project to work on Airline Flight Agenda Scheduling problem using shortest path algorithm.<\/p>\n\n\n\n

Here in this blog I am going to explain the implementation of Dijkstra\u2019s Algorithm for creating a flight scheduling algorithm and solving the problem below, along with the Python code.<\/p>\n\n\n\n

And, if you are in a hurry, here is the GitHub repo link of the project<\/a>.<\/p>\n\n\n\n

Problem Statement – Airline Flight Scheduling Algorithm<\/h2>\n\n\n\n

A travel agent requests software for making an agenda of flights for clients. The agent has access to a data base with all airports and flights. Besides the flight number, origin airport and destination, the flights have departure and arrival time. Specifically the agent wants to determine the earliest arrival time for the destination given an origin airport and start time.<\/em><\/p>\n\n\n\n

A few Google search and I found out, the problem was similar to the airline flight agenda scheduling problem example given here in this page<\/a>.<\/p>\n\n\n\n

Problem Overview – Shortest Path Algorithm<\/h2>\n\n\n\n

This is the shortest path algorithm problem as we need to calculate the earliest arrival time, with a given start time. So, we can take the problem as a di graph where all the airports are nodes and the flights are the di edges with weight of time interval i.e. the time difference between arrival time of destination airport and departure time of source airport.<\/p>\n\n\n\n

Here we need to take care that while going from origin airport to destination airport, and while taking flights from one airport to another, we can take only those flights which can be caught.<\/p>\n\n\n\n

So, time plays an important role in this problem as we can take only the flights whose departure time from the airport is later than our arrival time at the airport.<\/p>\n\n\n\n

So, to solve this we use Dijkstra\u2019s Algorithm with a little modification.<\/p>\n\n\n\n

Dijkstra\u2019s Algorithm:<\/strong><\/h3>\n\n\n\n

Dijkstra\u2019s Algorithm is a shortest path algorithm used to calculate the shortest path between nodes in a graph. This algorithm was created and published by computer scientist Dr. Edsger W. Dijkstra. <\/p>\n\n\n\n

The algorithm exists in many variants. Dijkstra’s original algorithm was to find the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.<\/p>\n\n\n\n

Dijkstra\u2019s Algorithm Priority Queue<\/strong><\/h4>\n\n\n\n

In Dijkstra\u2019s algorithm, we start from a source node and initialize its distance by zero. Next, we push the source node to a priority queue with a cost equal to zero. After that, we perform multiple steps. <\/p>\n\n\n\n

In each step, we extract the node with the lowest cost, update its neighbors\u2019 distances, and push them to the priority queue if needed.<\/strong> <\/p>\n\n\n\n

Each of the neighboring nodes is inserted with its respective new cost, which is equal to the cost of the extracted node plus the edge we just passed through. We continue to visit all nodes until there are no more nodes to extract from the priority queue. Then, we return the calculated distances.<\/p>\n\n\n\n

Our Algorithm Explained – Dijkstra Algorithm Example Explained<\/h3>\n\n\n\n

The algorithm for this problem is the slight modification of Dijkstra\u2019s Algorithm. Here we have the database about airports and the flights. There is information about flight number, origin airport and destination, the flights have departure and arrival time. So, given origin and destination airports and start time we need to make our data structure properly to keep the data and find the shortest arrival time.<\/p>\n\n\n\n

Here the di graph is used where the airports are the vertices and flights are di-edges with weights: departure time and arrival time. The distance should be the function of earliest arrival times at airports. Then based upon those earliest arrival time, we use a minimum priority queue for airports. <\/p>\n\n\n\n

For the initial origin airport let the earliest arrival time be start time and for others it will be infinity in the beginning. Now, until the queue is not empty, adjacent loop is to be formed where we can only select the flights which can be caught, and we also want the flight with minimum arrival time. <\/p>\n\n\n\n

So, for that we create another priority queue of flights where its departure time should be later than arrival time of another flight at the airport. And we also use another variable time, which is used to update the flight priority queue. <\/p>\n\n\n\n

And finally, we perform relaxation, where if the above time is less than the earliest arrival time at adjacent airport, then we change the earliest arrival time of the airport to be the time and update in the airport queue accordingly.<\/p>\n\n\n\n

Lets Code – Dijkstra Algorithm Python Code<\/h2>\n\n\n\n

I use VS Code and its my favorite code editor. Which one is yours?<\/p>\n\n\n

\n\t\t\t\t\t\t\t

<\/p><\/div>

<\/div>
<\/div><\/div>
<\/div><\/div>
<\/div><\/div>
<\/div><\/div>
<\/div><\/div><\/div><\/div><\/div>
Which is your favorite code editor?<\/h5><\/div>