Implementation and application of algorithms for shortest path problem

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.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