Analiza i primjene Dijkstrinog algoritma

završni rad

• Naslov (engleski): Dijkstra Algorithm, Analysis and Applications
• Autor: Mislav Jurić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2016-07-11, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: 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
• Ključne riječi (engleski): Dijkstra's algorithm; uniform-cost search; breadth-first search; depth-first search; iterative-depth search; transition cost; transition function; completeness; optimality
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:543709
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 09:31:49