Najkrajše poti z enim virom v dinamičnih grafihProšek, Anže (Avtor) Fürst, Luka (Mentor) Grafdinamični grafDijkstraalgoriteminkrementalnidekrementalniIskanje 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.20242024-08-29 13:20:08Diplomsko delo/naloga160512VisID: 37542COBISS_ID: 208529667sl