20.500.12556/RUL-160512 Najkrajše poti z enim virom v dinamičnih grafih Single-Source Shortest Paths in Dynamic Graphs Iskanje najkrajših poti z enim virom v uteženih grafih je klasičen problem na področju algoritmov in podatkovnih struktur. Ta problem lahko rešujemo z znanim Dijkstrovim algoritmom. V diplomski nalogi pa obravnavamo različico problema, pri kateri se v vsakem koraku lahko spremeni teža neke povezave grafa, lahko pa se povezava tudi doda ali odstrani. Seveda lahko problem rešimo tako, da po vsaki spremembi poženemo Dijkstrov algoritem, vendar pa obstajajo tudi učinkovitejši pristopi. V okviru diplomske naloge se ukvarjamo s t.i. inkrementalnim in dekrementalnim algoritmom: prvi obravnava vstavljanje nove povezave in znižanje teže obstoječe povezave, drugi pa odstranjevanje in zvišanje teže obstoječe povezave. Oba algoritma smo implementirali in preizkusili z različnimi testnimi scenariji. Finding the shortest paths from a single source in weighted graphs is a classic problem in the field of algorithms and data structures. This problem can be solved using Dijkstra's algorithm. However, in this thesis, we deal with a version of the problem in which the graph can be continuously updated. In particular, in each step, one of the edge weights can be modified, or an edge can be added or removed. Of course, we could run Dijkstra's algorithm after each update, but there are also more efficient approaches. In the thesis, we describe the so-called incremental and decremental algorithms; the former handles edge insertions and weight decreases, and the latter deals with edge removals and weight increases. We implemented both algorithms and tested them using different test scenarios. Graf dinamični graf Dijkstra algoritem inkrementalni dekrementalni Graph dynamic graph Dijkstra algorithm incremental decremental true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2024-08-29 13:20:08 2024-08-29 13:20:12 2024-09-23 12:46:09 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37542 208529667 Prosek_Anze_-_Najkrajse_poti_z_enim_virom_v_dinamicnih_grafih.pdf Prosek_Anze_-_Najkrajse_poti_z_enim_virom_v_dinamicnih_grafih.pdf 1 77829E30A7F863AE24358A8AACE0BFB1 58a9e56fdf87547d3e1915ce9ed2ee621dff7cec5ca784f1ae5facd22fe7d71c 6d652e2f-65f8-11ef-8f74-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=189228 Fakulteta za računalništvo in informatiko 0 0 0