Search

Algorithms for finding shortest paths in large graphs form an essential part of many modern navigation and routing systems. In vehicular navigation, the problem is compli- cated by dynamic nature of the network caused by road closures and changes in traffic, preventing application of many common speed-up techniques. The aim of this thesis is to design an algorithm for finding paths in large graphs that gains efficiency and scalability by minimizing the number of visited graph objects in storage. This was achieved by itera- tively simplifying the graph into a multi-layered approximative structure, and developing a modification of Dijkstra's algorithm that allow efficient navigation in the structure. The results show that the proposed method examines 4× less graph objects than A* and 14× less than Dijkstra, achieving better performance at the cost of slightly longer discovered paths. Additionally, the layered structure is able to accommodate changes in the base graph, allowing the algorithm to work on a changing network without costly recomputations. 1

This thesis deals with the design of programming language specialized in visu- alisation of graph algorithms, creating its interpreter and integrated development environment. The aim was to make the created program usable for education of graph algorithms and their implementation, especially at high school. Based on didactic knowledge, we designed language similar to Pascal, but adapted for the needs of graph algorithms. Part of the thesis is also brief introduction to inter- preters and several exemplary graphs and algorithms ilustrating work with our program. 1