Algoritmi najkraćeg puta u teoriji grafova s primjenom u umjetnoj inteligenciji

undergraduate thesis

• Title (english): Shortest path algorithms in graph theory with application in artificial intelligence
• Author: Branimir Medvedec
• Mentor: Josipa Pina Milišić (mentor)
• Committee member: Josipa Pina Milišić (predsjednik povjerenstva)
• Committee member: Andrea Aglić Aljinović (član povjerenstva)
• Committee member: Lana Horvat Dmitrović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-06-30, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Algoritmi najkraćeg puta su temeljni alati u teoriji grafova i igraju važnu ulogu u područjima poput navigacije, prometa i umjetne inteligencije. U ovom radu proučavamo Dijkstrin algoritam, A* algoritam i tehniku dvosmjernog pretraživanja. Dijkstrin algoritam pronalazi najkraći put u grafu koristeći težine rubova, dok A* algoritam koristi heuristiku za efikasniju pretragu. Tehnika dvosmjernog pretraživanja istovremeno pretražuje izvor i odredište u grafu. Algoritmi najkraćeg puta imaju široku primjenu u navigacijskim sustavima, analizi podataka i umjetnoj inteligenciji, pružajući efikasne alate za optimizaciju ruta i planiranje putovanja.

Abstract (english)

Shortest path algorithms are fundamental tools in graph theory and play a significant role in areas such as navigation, transportation, and artificial intelligence. In this paper, we study Dijkstra's algorithm, the A* algorithm, and the bidirectional search technique. Dijkstra's algorithm finds the shortest path in a graph by considering edge weights, while the A* algorithm employs heuristic functions for more efficient search. The bidirectional search technique simultaneously explores the source and destination in the graph. Shortest path algorithms have wide applications in navigation systems, data analysis, and artificial intelligence, providing efficient tools for route optimization and trip planning.

• Keywords: Algoritmi najkraćeg puta; Dijkstrin algoritam; A* algoritam; dvosmjerno pretraživanje; navigacija; optimizacija ruta; planiranje putovanja; umjetna inteligencija
• Keywords (english): Shortest path algorithms; Dijkstra's algorithm; A* algorithm; bidirectional search; navigation; route optimization; trip planning; artificial intelligence
• Language: croatian
• URN:NBN: urn:nbn:hr:168:257421
• 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-07-13 10:21:52