Implementation and Comparative Analysis of the Dijkstra's Algorithm on the Base of Distinct Priority Queues

This study considers the problem of finding the shortest path on graphs. This problem is implemented using Dijkstra's algorithm based on various priority queues. Many researches and developments on this topic have been done, but nevertheless the problem has not been covered in full scope. This paper presents basic models of the research object in the form of distance matrices describing the given graph and mapping a set of vertices. Presented the model of visualization of the given graph and the optimal network constructed with the help of Dijkstra's algorithm. This work includes practical realization of the solution of the task in the form of program which realizes the work of Daikstra's algorithm. The program code includes the implementation of a selected set of heaps, with experimental studies. Structure of the work: The graduate qualification work consists of an introduction, five sections, a conclusion and a list of references. The introduction gives a general description of the work, justifies the relevance of research, formulates the purpose of the work, reveals the scientific novelty and practical significance of the results. Also presented a brief overview of the content of the work by sections. In the first section, a statement of the problem is made, a description of Dijkstra's algorithm is given, and various priority queues (heaps) are considered. The second section gives a theoretical analysis of the problem. Given a basic model of the research object in the form of a distance matrix describing a given graph, as well as an output binary matrix which is used to represent a set of vertices included in the path from the chosen vertex to other vertices of the graph. The model of visualization of the given graph and the optimal network constructed with the help of Dijkstra's algorithm is also presented. The third section gives a detailed description of the methodology for solving the problem. In the fourth section, gives a practical realization of the solution of the task in the form of the program implementing the work of Dijkstra's algorithm and also including realization of the selected set of heaps in order to carry out experimental research. The fifth section describes the experiments carried out to estimate the running time of Dijkstra's algorithm using synthesized priority queues. Conclusions are formulated and recommendations for their use are given. In the conclusion, the main results of the conducted research are presented in detail.