AN ADVANCED FLIGHT SCHEDULING APPLICATION BASED ON DIJKSTRA'S ALGORITHM

Aradhana Iris Singh, Hepzibah Christinal A.

Karunya Institute of Technology and Sciences, Coimbatore 641114

 

ABSTRACT

Dijkstra's Algorithm is a popular example of a greedy solution to the problem of determining the shortest path. This algorithm calculates the most direct and shortest journey and is majorly used in routing, rail networks, maps, etc. Its application to both directed and undirected graphs has the same goal, which is to determine the path that travels the least distance from the starting node, also known as the origin node, to any other node along the tracks. In this article, we are going to implement an application of this algorithm, but this time with a minor tweak. a travel agency asks for software that can create flight schedules for their customers, and the agent has the access to a database that lists all of the airports and flights. In this scenario, the agent is able to create flight schedules for their customers. In addition to the flight number, the airport of departure and arrival, and the destination, each trip's times of departure and arrival are listed. The agent is interested in finding out the earliest possible arrival time at the destination, given both the airport of departure and the time at which the trip will begin. It was observed during implementation that, if the method is correctly applied, the overall cost for building every flight priority queue is O(m). For the airport priority queue, the overall cost using a heap is O((n + m) log n)).

Keywords: Dijkstra's Algorithm, greedy approach, priority queue, flight schedules

 

1.      INTRODUCTION

Dijkstra's approach is used to find the shortest routes between the nodes that make up a graph, such as a road network. The concept was first presented in 1956 by Dutch computer scientist Edsger W. Dijkstra, who published it in 1960.

There are several iterations of the algorithm. A typical form of Dijkstra's technique fixes a single node as the "source" node and seeks the shortest routes from the source to all other nodes in the graph, yielding a shortest-path tree. The algorithm determines the path of least resistance from a particular source node in the network to every other node in the graph. By pausing the process once the shortest path to the destination node has been identified, it may also be used to identify the shortest pathways from a single source node to a single destination node.

To find the minimal shortest path among the cities, the Dijkstra’s algorithm is often used for example, where the edge path costs correspond to the driving distances between cities connected by a direct road and the nodes of the graph are cities. Network routing protocols, commonly make use of shortest path algorithms. It functions as a subroutine in a number of algorithms, notably Johnson's.

Labels for the Dijkstra algorithm must be positive integers or real values that are completely sorted. The approach possibly be extended for use any partly ordered labels as long as the successive labels (a subsequent label is formed while passing through an edge) are consistently increasing. The generalized Dijkstra shortest-path algorithm is the moniker for this overall concept.

Dijkstra's method employs a data structure to store and retrieve partial solutions in descending o

rder of distance from the initial state. Dijkstra's method, or a derivation of it, is often as uniform cost search in those other fields, such as artificial intelligence, and is characterized as an example of the more generic best-first search principle.

 

2.      PRELIMINARIES:

Serial no.	Name of the paper	Name of the authors	Observation
1.	An Investigation of Dijkstra and Floyd Algorithms in National City Traffic Advisory Procedures	Arun Kumar Sangaiah ,Minghao Han , Suzi Zhang	The blueprint and its execution of the National City traffic advisory processes are the main topics of this essay. The major goal of this article is to give passengers the best decision-making and transportation counseling process.
2.	The Improved Dijkstra's Shortest Path Algorithm and Its Application	Wang Shu-Xi	This research conducted a number of focused tests and offered an improved approach.The trials' findings show that the modified algorithm can solve both the digraph and digraph shortest path challenges.
3.	Point-to-Point Shortest Path Algorithms with Preprocessing	Andrew V. Goldberg	This paper studies recent heuristics that address the issue while only looking at a portion of the input graph, which may be quite large.
4.	Analysis of Dijkstra’s Algorithm and A* Algorithm in Shortest Path Problem	Dian Rachmawati and Lysander Gustin	The purpose of this study is to contrast these two approaches to finding the shortest path. Dijkstra and A* perform nearly equally well, but A* outstand better when used to solve a large-scale plan.
5.	An algorithm of shortest path based on Dijkstra for huge data.	Zhang Fuhao, Liu Jiping	This paper revolves around a novel approach based on the topological relationship of the vector data to provide network analysis for big data sets in practice.The paper first provides a thorough introduction to the Dijkstra method before recommending network analysis for large amounts of data.
6.	An Experiment on the Performance of Shortest Ptheath Algorithm	Simon Chan Yew Meng, Nur’ayuni Adnan, SyazwanSyafiqahSukri, and Wan Mohd Nazmee Wan Zainon	The main aimof this paper is to research and test different shortest path. The shortest route algorithm and each of its implementation techniques were summarized in this work.
7.	Shortest Path Analysis Based on Dijkstra’s Algorithm in Myanmar Road Network	Yi Yi Win, Hnin SuHlaing , Tin Tin Thein	This paper includes Dijkstra's method to find the bus route which is the shortest.
8.	Applying Dijkstra’s Algorithm in Routing Process	Nitin Gupta, Kapil Mangla,Anand Kumar Jha ,Md. Umar	This paper discusses about the different uses and applications of Dijkstra’s Algorithm
9.	Recent Applications of Dijkstra’s Algorithm in the Process of Production Planning	Marcel Behún, DušanKnežo, Michal Cehlár, Lucia Knapˇcíková, and AnnamáriaBehúnová	In order to calculate the extracted raw materials in terms of usage, this study will design a system that takes into account both the extraction location and the consumption location.

 

 

3.      Methodology:

Dijkstra's technique constructs a collection of nodes with the least distance from the source node and then uses this information to establish the shortest path tree.

The only graphs that Dijkstra's Algorithm may use are those with positive weights. This is due to the fact that in order to identify the shortest path, the weights of the edges must be added during the procedure. The algorithm won't function properly if the network contains a negative weight. The current route to a node is designated as the quickest route to that node once it has been registered as "visited." If the overall weight may be decreased after this step, negative weights can change this.

Pseudo code:

 i.            Dijkstra(Graph, source): //function

ii.            for each vertex vertex in Graph.vertices:

iii.            dst[vertex] ← INFINITY

iv.            prev[vertex] ← UNDEFINED

v.            add vertex to S

vi.            dst[source] ← 0

vii.            while S isn’t empty:

viii.            U← vertex in S with min dst[a]

ix.            removing a from S

x.            for each neighbor vertex of a still in S:

xi.            alternate ← dist[a] + Graph.Edges(a, vertex)

xii.            if alternate<dist[ver]:

xiii.            dst[vertex] ← alternate

xiv.            prev[vertex] ← a

xv.            return dst[], prev[]

 

The search can be terminated after line 10 if u equals target if our only goal is to determine the shortest path between the vertices source and target. We can now find the shortest route from the start node to the target node using the reverse iteration method:

1.      St←  thesequence is taken empty

2.       u ← is of the target

3.      ifprev[u] is defined or u = source: // if the vertex ver is reachable

4.      while u is defined:

// constructing the shortest path with a stack St

5.      insert u at the beginning of St/ Push the vertex onto the stack

6.      u ← prev[u]  // Traverse from target to source

Now, sequence St is either the collections of vertices that make up either of the shortest pathways from source to target, or it is the empty sequence if there is no such path.

4.      Proposed Method:

In Dijkstra's method, we begin with a source node and set its distance as zero at the beginning of the process. After that, the source node is added to a priority queue that has a cost of $0 and is pushed there. After that, we go through a series of phases.

In order to determine which node should come next in the exploration process, Dijkstra's method requires a priority queue. The most up-to-date information on a node's total distance is used to determine its "priority" when it comes time to add it to the priority queue. If we discover a route that takes us to a node that is shorter in the future, the priority of the node can be modified to reflect the new total distance. We also want to be able to identify and eliminate the node with the shortest total distance when Dijkstra's algorithm concludes that the node's presently total distance must be its best-possible total distance. This is done so that we can identify the node with the smallest overall distance.At each stage, we take out the node that has the lowest cost, then we check and adjust the distances of its neighbors, and if necessary, we add them to the priority queue.

Each of the nearer nodes is placed with its own unique new cost, which is equal to the sum of the cost of the node that was removed plus the cost of the edge that we most recently traversed. We will proceed to visit each of the nodes until the priority queue has no more nodes that can be extracted from it. After that, we provide you the results of the distance calculations.

Dijkstra's Algorithm, with a few tweaks here and there, provides the basis for the solution to this particular problem. This is the database that contains information on flights and airports. There is information on the flight number, the airport of departure, as well as the airport of arrival, and the departure and arrival times for each flight. Therefore, given the airports of origin and destination as well as the start time, we need to construct an appropriate data structure in order to store the data and locate the earliest possible arrival time.In this case, a digraph is utilized, with airports serving as the vertices and flights acting as di-edges with weights denoting their respective departure and arrival times. It is important that the distance be calculated based on the earliest arrival times at each airport. After that, we implement a minimal priority queue at airports, and its placement is determined by the earliest arrival time.The earliest arrival time should be used as the start time for the first origin airport, whereas for all other airports it should initially be set to infinity. Now, in order to ensure that the queue does not become empty, an adjacent loop has to be constructed. In this loop, we will only be able to choose flights that can be caught, and we also want the aircraft that has the quickest arrival time.

Therefore, in order to accommodate this, we have established a second priority queue for flights, and the departure time of this queue's planes must be after than the arrival time of any other aircraft at the airport. In addition to that, we make use of a different variable time that is applied to the process of updating the flight priority queue.

 

Figure 1: Flowchart of Dijkstra’s Algorithm

Finally, if the time specified earlier is earlier than the earliest arrival time at a nearby airport, we practice loosening, which changes the airport's earliest arrival time to the time in question. The relevant modifications are then made in the airport line using this input.

 

Figure 2: Assumed graph

 

In the above graph, figure 2, there is a flight flies from the airport A at 2 and reaches C at 8 and at 2, there leaves another flight from airport A and reaches airport B at 6, and the rest.

 

We can go to Airport B and C from A. The best possible arrival time for airports B and C would be 6 and 8 respectively. The flight from C to D departs at 6. There is no chance we can make that flight if we leave at two and arrive at airport C at 8. So, from C we can only and only reach to  B. We can reach airport B either from A or from C, but the earliest arrival time would be from airport A at 6. Similarly, we can go to D or E airports or any other airports through B.

Ultimately, we may reach airport E from airport A following the algorithm's best and shortest route and the path would be via route A to B to D and to E.

Figure 3: Path followed using Dijkstra’s Algorithm

 

And if we take these planes, we would arrive at airport E at 14, which is the time that our programme estimates we will get there, as shown in figure 3. This method has been used to great effect in order to effectively implement the Dijkstra's Algorithm, which can be outlined to solve this problem of arranging airline flight routes which can be another application.

 

5.      Results and Discussion:

Calculating the price is challenging due to the added cost associated with creating all of the flight priority queues. In the worst scenario, we may suppose that building each priority queue will cost O(m) in the event of m flight priority queues. Therefore, the overall cost of creating all the flight priority queues is O(m2). There is not much argument that this is an extremely high upper bound. The explanation is that, in the worst-case scenario, there wouldn't be priority lines with m flights in each. Another perspective on the counting is provided by the fact that each edge is only assigned to one flight priority queue. If the technique is correctly applied, the overall value for building all of the flight priority queues is given by O(m). The overall cost of using in a large amount for the airport priority queue is O((n + m) log n)

 

In this section, the user can specify the source node and the destination node. According to the findings of the study, it is possible, with the help of DIJKSTRA'S method, to simply compute the shortest path and the shortest distance from the source node to the destination node. It proceeds to the node that is the destination after continually picking up the nodes that are the shortest distance away. Once it has arrived at the target node, it will display the route that covers the shortest distance.

 

 

 

 

 

 

6.      Conclusion:

In this section, the user can specify the source, i.e. the starting node, and the destination, i.e. the ending node. According to the findings of the study, it is possible, with the help of DIJKSTRA'S method, to simply compute the shortest path andthe distance which is shortest between the source and destination nodes. It proceeds to the node that is the destination after continually picking up the nodes that are the shortest distance away. Once it has arrived at the target node, it will display the route that covers the shortest distance.

 

Reference:

[1] Shivani sanan, Leena jain, Bharti kappor : Shortest Path Algorithm, International Journal of Application or Innovation in Engineering & Management (IJAIEM) , vol 2 , issue 7, July 2013, page 316-320.

 [2] Bharath Uppalancha, Kranthi: Optimizing the Robot’s path using Dijkstra’s Algorithm, International Journal of Innovative Research in Science,Engineering and Technology (IJIRSET),Vol. 4, Issue 6, June 2015

[3]https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

[4] Huijuan Wang et. al , “Application of Dijkstra algorithm in robot path-planning”, Second International Conference on Mechanic Automation and Control Engineering (MACE), pp. 1067 - 1069 ,2011

[5] Abhishek Goyal, Prateek Mogha,RishabhLuthra,Ms. Neeti Sangwan “Path Finding:A* or Dijkstra’s?”, International Journal of Management,IT and Engineering (IJMIE)ISSN: 2249-0558,Volume 4, Issue 7,July 2014

[6] Charika Jain, Jitendra Kumawat: Processing Delay Consideration in Dijkstra’s Algorithm, International Journal of Advanced Research in Computer Science and Software Engineering, Volume 3, Issue 8, August 2013[1]

[7] Tolga YÜKSEL Abdullah SEZGİN, An Implementation Of Path Planning Algorithms For Mobile Robots On A Grid Based Map, OndokuzMayısUniversity , Electrical & Electronics Engineering Department , 55139 Kurupelit-SAMSUN-TURKEY

[8] PimploiTirastittam, PhutthiwatWaiyawuththanapoom, Public Transport Planning System by Dijkstra Algorithm: Case Study Bangkok Metropolitan Area, International Journal of Social, Behavioral, Educational, Economic, Business and Industrial Engineering Vol:8, No:1, 2014

[9]http://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf.

[10]http://www.csl.mtu.edu/cs2321/www/newLectures/30_More_Dijkstra. htm