Implementacija i primjena algoritama za problem najkraćeg puta

završni rad

• Naslov (engleski): Implementation and application of algorithms for shortest path problem
• Autor: Karla Udiljak
• Mentor: Lana Horvat Dmitrović (mentor)
• Član povjerenstva: Lana Horvat Dmitrović (predsjednik povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (član povjerenstva)
• Član povjerenstva: Mate Puljiz (č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: 2023-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: graf; problem najkraćeg puta; algoritmi za pronalazak najkraćeg puta; A*; Dijkstra
• Ključne riječi (engleski): graph; shortest path problem; shortest path algorithms; A*; Dijkstra
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:982276
• 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: 2023-07-13 10:38:17