Algoritmi pronalaženja najkraćeg puta u grafu

undergraduate thesis

• Title (english): Algorithms for Finding the Shortest Path in a Graph
• Author: Mateja Potak
• Mentor: Marin Šilić (mentor)
• Committee member: Marin Šilić (predsjednik povjerenstva)
• Committee member: Helena Čeović (član povjerenstva)
• Committee member: Adrian Satja Kurdija (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-06-28, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Algoritmi pronalaženja najkraćeg puta u grafu dijele se ovisno o strategiji pretraživanja na algoritme slijepog i algoritme usmjerenog pretraživanja. Algoritmi usmjerenog pretraživanja u obzir uzimaju i heuristiku koja nastoji usmjeriti brže k cilju. U radu su obrađena četiri algoritma i njihova programska ostvarenja. U algoritme slijepog pretraživanja spada pretraživanje s jednolikom cijenom (UCS), a u algoritme usmjerenog pretraživanja spadaju pretraživanje „najbolji prvi“, pretraživanje usponom na vrh te algoritam A*. Napravljen programski sustav nastoji oponašati Google Maps za 15 spremljenih konkretnih mjesta u Zagrebu te nudi korisniku mogućnost pretraživanja najkraćeg puta od zadanog početnog do ciljnog mjesta koristeći navedene algoritme. Cilj pretraživanja je optimizacija vremena ili optimizacija udaljenosti.

Abstract (english)

Algorithms for finding the shortest path in a graph are divided depending on the search strategy into uninformed and informed search algorithms. Informed search algorithms also take into account heuristics that try to direct the search faster to the goal. The paper describes four algorithms and their implementation. Uninformed search algorithms include uniform-cost search (UCS) and informed search algorithms include greedy best-first search, hill-climbing search and the A* algorithm. The created program system tries to imitate Google Maps for the stored 15 specific places in Zagreb. It offers the user the possibility to search for the shortest path from the chosen starting point to the destination point using the specified algorithms. The goal of the search is time optimization or distance optimization.

• Keywords: algoritmi pronalaženja najkraćeg puta u grafu; pretraživanje s jednolikom cijenom; algoritam "najbolji prvi"; pretraživanje usponom na vrh; algoritam A*; Google Maps; prostorna optimizacija; vremenska optimizacija
• Keywords (english): algorithms for finding the shortest path in a graph; uniform cost search; greedy best-first search; hill-climbing search; A* algorithm; Google Maps; spatial optimization; time optimization
• Language: croatian
• URN:NBN: urn:nbn:hr:168:586292
• 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: 2023-10-11 10:12:32