20.500.12556/RUL-183073 Primerjava algoritmov za iskanje najcenejše poti v grafu Comparison of algorithms for finding the shortest path in a graph Diplomska naloga obravnava primerjavo algoritmov za iskanje najcenejše poti v grafu. V delu je predstavljena primerjava teoretične časovne zahtevnosti algoritmov in njihove zmogljivosti pri praktični implementaciji. Naloga je razdeljena na štiri vsebinske sklope. Najprej je podan pregled petih obravnavanih algoritmov – Dijkstrovega algoritma z dvojiško kopico, Dijkstrovega algoritma s Fibonaccijevo kopico, Bellman–Fordovega algoritma, Johnsonovega algoritma in Floyd–Warshallovega algoritma – skupaj z opisom njihovega delovanja in teoretično časovno zahtevnostjo. V drugem sklopu so opisane testne množice, ki se delijo na umetno generirane grafe in standardne grafe iz zbirke SNAP, ki predstavljajo realna omrežja. Tretji sklop opisuje testno okolje ALGator, v katerem so bili izvedeni vsi eksperimenti. Četrti sklop predstavlja pregled in primerjavo rezultatov testiranjater diskusijo ugotovitev. Pri analizi rezultatov je poudarek na iskanju odstopanj od teoretično pričakovanih vrednosti in njihovi razlagi. Izpostavljeni sta dve glavni odstopanji. Prvo je obnašanje Dijkstrovega algoritma: implementacija z dvojiško kopico se v praksi izkaže za hitrejšo od implementacije s Fibonaccijevo kopico, Čeprav ima slednja boljšo teoretično časovno zahtevnost. Razlog so višji konstantni faktorji in slabša krajevna lokalnost podatkov v predpomnilniku pri Fibonaccijevi kopici. Drugo odstopanje smo opazili pri grafih z več kot milijon vozlišči in izjemno nizko gostoto, kjer Johnsonov algoritem preseže Bellman-Fordovega, čeprav ima slednji boljšo asimptotično zahtevnost. The thesis addresses a comparison of algorithms for finding the shortest (cheapest) path in a graph. The work presents a comparison of the theoretical time complexity of the algorithms and their performance in practical implementation. The thesis is divided into four thematic sections. First, we provided an overview of the five algorithms under consideration — Dijkstra’s algorithm with a binary heap, Dijkstra’s algorithm with a Fibonacci heap, the Bellman–Ford algorithm, Johnson’s algorithm, and the Floyd–Warshall algorithm — along with a description of how they work and their theoretical time complexity. In the second section, we described the test datasets, which are divided into artificially generated graphs and standard graphs from the SNAP dataset collection, representing real-world networks. The third section describes the ALGator testing environment, in which all experiments were carried out. The fourth section presents an overview and comparison of the test results, along with a discussion of the findings. In analyzing the results, we placed emphasis on identifying deviations from theoretically expected values and explaining them. We highlighted two main deviations. The first concerns the behavior of Dijkstra’s algorithm: the implementation with a binary heap proves to be faster in practice than the implementation with a Fibonacci heap, even though the latter has better theoretical time complexity. The reason lies in the higher constant factors and poorer cache locality of the Fibonacci heap. The second deviation was observed in graphs with more than one million vertices and an exceptionally low density, where Johnson’s algorithm outperforms Bellman–Ford, despite the latter having better asymptotic complexity. algoritmi grafi primerjava najcenejše poti implementacija empirično vrednotenje algorithms graphs comparison shortest paths implementation empirical evaluation true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2026-06-03 12:10:03 2026-06-03 12:10:13 2026-06-10 08:56:33 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38753 281070851 Golob_Lan_-_Primerjava_algoritmov_za_iskanje_najcenejse_poti_v_grafu.pdf Golob_Lan_-_Primerjava_algoritmov_za_iskanje_najcenejse_poti_v_grafu.pdf 1 06D86C1F21273A0D485122BA99A2F64D 1bf301e3e1e263e6a167182b4e8a1977f8cabe0f5270a618538f93e1e0a7a4e1 0c974c9a-5f34-11f1-b0ab-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=234903 Fakulteta za računalništvo in informatiko 0 0 0