Application of Graph Algorithms for Finding Optimal Route on Geo. Maps

Glavna tema ovog rada su graf algoritmi za pronalaženje najkraće rute na mapama. U prvom poglavlju denirat ćemo graf u matematičkom smislu, spomenuti i objasniti vrste grafova te dati par primjera različitih tipova grafova.U drugom dijelu poglavlja predstavit ćemo načine reprezentacije grafa u memoriji računala. U drugom poglavlju denirat ćemo šetnju kroz graf i putove u grafu. Nakon toga ćemo pojasniti obilazak grafova pomoću pretraživanja grafa po širini i dubini.Objasnit ćemo problem najkraćeg puta, raspisati Dijsktrin algoritam i na osnovu njega izvesti tehnike ubrzavanja kao što su dvosmjerno pretraživanje, A* i ALT.The main topic of this thesis are shortest path graph algorithms. In the rst part of the paper we shall dene a graph in mathematical sense, mention and explain types of graphs and give some examples of dierent graphs. In the second part of the rst chapter we'll present how to store or represent graph in comupter memory. In the second part we shalll dene walk and paths in graph. After that Breadth-First Search and Depth-First Search is presented. We'll explain shortest path problem, write out Dijkstra's algorithm and presented speed-up techniques such as bidirectional search, A* and ALT