Implementacija i primjena algoritama za problem najkraćeg puta

undergraduate thesis

• Title (english): Implementation and application of algorithms for shortest path problem
• Author: Karla Udiljak
• Mentor: Lana Horvat Dmitrović (mentor)
• Committee member: Lana Horvat Dmitrović (predsjednik povjerenstva)
• Committee member: Ana Žgaljić Keko (član povjerenstva)
• Committee member: Mate Puljiz (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem najkraćeg puta modelira se pomoću grafova, a svodi se na traženje podgrafa s najmanjom težinom. Dijeli se na četiri varijante: najkraći put od jednog početnog vrha do svih ostalih, od svih ostalih do jednog odredišnog, između jednog para vrhova te između svih parova vrhova u grafu. Detaljno su objašnjeni algoritmi BFS, Dijkstrin i Bellman-Ford koji rješavaju prva dva navedena tipa problema, Floyd-Warshall i Johnson se primjenjuju kod četvrte varijante problema te A* koji pronalazi najkraći put kod trećeg navedenog tipa problema. Problem svoju primjenu nalazi u navigaciji kao što je to Google Maps, komunikacijskim sustavima, Internet usmjeravanju, društvenim mrežama i brojnim drugim. U sklopu rada implementirani su i uspoređeni Dijkstrin i A* algoritmi na jednostavnom navigacijskom programu.

Abstract (english)

The shortest path problem is modeled using graphs, and is based on searching for the subgraph with the smallest weight. Four types of shortest path problem are: Single-Source Shortest-Path Problem, Single-Destination Shortest-Path Problem, Single-Pair Shortest-Path Problem and All-Pairs Shortest-Path Problem. The explained algorithms are BFS, Dijkstra and Bellman-Ford algorithms that solve the first two types of problems, Floyd-Warshall and Johnson used for the fourth variant of the problem, and A*, which finds the shortest path for the third type of problem. The problem finds its application in navigation such as Google Maps, communication systems, Internet routing, social networks and many others. As part of the work, Dijkstra's and A* algorithms were implemented and compared on a simple navigation program.

• Keywords: graf; problem najkraćeg puta; algoritmi za pronalazak najkraćeg puta; A*; Dijkstra
• Keywords (english): graph; shortest path problem; shortest path algorithms; A*; Dijkstra
• Language: croatian
• URN:NBN: urn:nbn:hr:168:982276
• 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:38:17