Download
PDF 534.74 KB
undergraduate thesis
30   12
Application of Graph Algorithms for Finding Optimal Route on Geo. Maps
Danilo Šormaz (2016)
Josip Juraj Strossmayer University of Osijek
Department of Mathematics
Chair of Applied Mathematics
Computer Science Research Group
Metadata
TitlePrimjena graf algoritama za pronalaženje optimalne rute na mapama
AuthorDanilo Šormaz
Mentor(s)Domagoj Matijević (thesis advisor)
Abstract
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.
KeywordsGraphs shortest path problem route planning Breadth-First Search Depth-First Search
Parallel title (English)Application of Graph Algorithms for Finding Optimal Route on Geo. Maps
GranterJosip Juraj Strossmayer University of Osijek
Department of Mathematics
Lower level organizational unitsChair of Applied Mathematics
Computer Science Research Group
PlaceOsijek
StateCroatia
Scientific field, discipline, subdisciplineNATURAL SCIENCES
Mathematics
Mathematical Logic and Accounting
Study programme typeuniversity
Study levelundergraduate
Study programmeUniversity undergraduate study programme in mathematics
Academic title abbreviationuniv.bacc.math.
Genreundergraduate thesis
Language Croatian
Defense date2016-09-30
Parallel abstract (English)
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.
Parallel keywords (Croatian)Grafovi problem nakraćeg puta planiranje rute pretraživanje grafa po širini i dubini.
Resource typetext
Access conditionOpen access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
URN:NBNhttps://urn.nsk.hr/urn:nbn:hr:126:534030