Analiza i primjene Dijkstrinog algoritma

undergraduate thesis

• Title (english): Dijkstra Algorithm, Analysis and Applications
• Author: Mislav Jurić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Ana Žgaljić Keko (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Značajan razvoj algoritma pretraživanja usmjerenog grafa nalazimo 50-ih godina prošlog stoljeća. E. W. Dijkstra konstruirao je algoritam na temelju kojeg su kasnije proizašle različite inačice i poopćeni oblici. Svima je zajedničko otkrivanje puta, koji ne mora uvijek biti optimalan. Zbog nedostatka memorije umjesto pretraživanja s jednolikom cijenom, tj. pretraživanja u širinu, možemo koristiti pretraživanje u dubinu. Isto tako, imamo mogućnost kombiniranja prednosti obje vrste algoritma te time dobivamo algoritam iterativnog pretraživanja u dubinu. Svakodnevno se susrećemo s problemom pretraživanja usmjerenog grafa, često ni ne razmišljajući o tome. Prilikom povezivanja na Internet, ili korištenja aplikacije koja sadrži digitalni zapis karte, Dijkstrin algoritam i njegovi oblici, poput algoritma pretraživanja s jednolikom cijenom, osiguravaju nam njihovo nesmetano korištenje. E. W. Dijkstra posvetio je gotovo cijeli svoj život razvoju računarstva i na tome smo mu zahvalni.

Abstract (english)

Significant development of algorithms for finding the shortest paths between nodes in a graph has begun in 1950s. E. W. Dijkstra has conceived an algorithm, on which later on were based many others. All algorithms have in common discovering the path between two nodes, which sometimes is not the optimal one. Because of the lack of memory or computer resource, we prefer to use depth-first search instead of breadth-first search, in case of uniform transition costs. Furthermore, we can combine the benefits from each algorithm and therefore use iterative search in depth. Finding the shortest path is almost an everyday problem. For an example, it is used when we connect to the Internet or when we want to find directions on digital map. In these cases, uniform-cost search algorithm does all the work in the background. E. W. Dijkstra has dedicated his whole life to computer science and its development and we are very thankful for that.

• Keywords: Dijkstrin algoritam; pretraživanje s jednolikom cijenom; pretraživanje u širinu; pretraživanje u dubinu; iterativno pretraživanje u dubinu; cijena prijelaza; funkcija prijelaza; potpunost; optimalnost
• Keywords (english): Dijkstra's algorithm; uniform-cost search; breadth-first search; depth-first search; iterative-depth search; transition cost; transition function; completeness; optimality
• Language: croatian
• URN:NBN: urn:nbn:hr:168:543709
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 09:31:49