Brzi algoritmi za problem najkraćeg puta

master's thesis

• Title (english): Fast algorithms for the shortest path problem
• Author: Andrija Mandić
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Zvonko Iljazović (član povjerenstva)
• Committee member: Matija Kazalicki (član povjerenstva)
• Committee member: Ilja Gogić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-09-22, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Problem pronalaska najkraćeg puta u grafu široko je primjenjiv u stvarnom svijetu. Mnoge se stvari matematički modeliraju pomoću grafova čime se stvara potreba za što boljim i bržim algoritmima za rješenje ovog problema. Primjeri su razne vrste prometnica i situacija u prometu, internetske mreže, posebne vrste baza podataka te razni drugi. Prvi dio rada posvećen je klasičnim algoritmima koji ne zahtijevaju prethodnu obradu podataka koju nazivamo predprocesiranje. Opisuju se Dijkstrin algoritam i A\( ^*\) algoritam te njihove dvosmjerne verzije. U novije vrijeme ključ ubrzanja pronalaska najkraćeg puta u algoritmima leži u fazi predprocesiranja. Algoritam provodeći potrebne postupke prikupi informacije koje koristi pri ubrzanju faze traženja puta. Detaljno opisujemo dva takva algoritma: Contraction Hierarchies i Landmark A\( ^*\). Contraction Hierarchies algoritam na prikladan način odreduje hijerarhiju vrhova, te u početni graf dodaje nove bridove zvane prečaci. Pronalazak najkraćeg puta provodi se dvosmjernim Dijkstrinim pretraživanjem u modificiranom grafu gdje obje pretrage pretražuju samo bridove koje vode do vrhova veće hijerarhije. Landmark A\( ^*\) algoritam temelji se na A\( ^*\) pretraživanju uz heurističku funkciju procjene udaljenosti dobivenu fazom predprocesiranja. Uvode se vrhovi orijentiri za koje je poznata udaljenost od i do svih preostalih vrhova. Procjena udaljenosti dobije se po uzoru na nejednakost trokuta. U zadnjem dijelu provodimo usporedbu promatranih algoritama te iznosimo neke implementacijske pojedinosti. Rezultati su dobiveni na podacima stvarnih cestovnih prometnica. Contraction Hierarchies nadmašuje Landmark A\( ^*\) algoritam u brzini pronalaska najkraćeg puta, no uz veće vrijeme predprocesiranja. Ovisno o dozvoljenom vremenu i raspoloživoj memoriji kod pripremne faze, bira se prikladniji algoritam. Oba algoritma su značajno brža u usporedbi s klasičnim Dijkstrinim pretraživanjem.

Abstract (english)

The problem of finding the shortest path in a graph is widely applicable in the real world. Many things are mathematically modeled using graphs, which creates the need for better and faster algorithms to solve this problem. Examples are various types of roads and traffic situations, Internet networks, special types of databases, and various others. The first part of this thesis is dedicated to classical algorithms that do not require preprocessing. The Dijkstra’s algorithm and the A\( ^*\) algorithm, and their two-way versions are described. More recently, the key to accelerating finding the shortest path in algorithms lies in the preprocessing phase. By performing the necessary procedures, the algorithm collects the information it uses to speed up the path search phase. We describe two such algorithms in detail: Contraction Hierarchies and Landmark A\( ^*\). The Contraction Hierarchies algorithm appropriately determines the hierarchy of vertices and adds new edges called shortcuts to the initial graph. The shortest path finding is performed by a two-way Dijkstra’s search in a modified graph where both searches search only the edges leading to the tops of the larger hierarchy. The Landmark A\( ^*\) algorithm is based on A\( ^*\) search with a heuristic distance estimation function obtained by the preprocessing phase. We introduce the landmark nodes for which the distance from and to all remaining nodes is known. The estimate of the distance is obtained based on the triangle inequality. In the last part, we compare the observed algorithms and present some implementation details. The results were obtained on the basis of actual road network data. Contraction Hierarchies outperforms the Landmark A\( ^*\) algorithm in the speed of finding the shortest path, but with a longer preprocessing time. Depending on the time allowed and the available memory during the preparation phase, a more suitable algorithm is chosen. Both algorithms are significantly faster compared to the classic Dijkstra’s search.

• Keywords: Dijkstrin algoritam; A\( ^*\) algoritam; Contraction Hierarchies; Landmark A\( ^*\)
• Keywords (english): Dijkstra’s algorithm; the A\( ^*\) algorithm; Contraction Hierarchies; Landmark A\( ^*\)
• Language: croatian
• URN:NBN: urn:nbn:hr:217:904493
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-10-29 09:28:21