Najkrajše poti v grafih z negativnimi utežmiKOMEL, VITA (Avtor) Fijavž, Gašper (Mentor) najkrajše potiBNW algoritemdekompozicija grafovV diplomski nalogi se ukvarjamo s problemom iskanja najkrajših poti v grafih z negativnimi utežmi. Bellman-Fordov algoritem, eden od klasičnih algoritmov za iskanje najkrajših poti v grafih z n vozlišči in m povezavami, zmore obvladovati tudi grafe z negativnimi utežmi. Toda njegova časovna zahtevnost O(mn) je znatno slabša, kot zahtevnost Dijkstrovega algoritma, ki je skoraj linearna O(m + n log n). Žal pa Dijkstrov algoritem ne obvlada grafov, v katerih bi imele povezave lahko tudi negativno dolžino. V delu predstavimo skoraj linearen verjetnostni algoritem, ki v času O(m p(log n + log W)) izračuna dolžino najkrajše poti med točkama v uteženem grafu, pri čemer je p polinom in W največja velikost negativne uteži. Prvi tak algoritem so predstavili Bernstein, Nanongkai in Wulff-Nielsen. Kmalu za objavo pa so izboljšan rezultat - tako v prezentaciji kot v redukciji logaritemskih faktorjev - predstavili Bringmann, Casiss in Fischer. Naloga predstavi idejo algoritma in obravnava problem najkrajših poti na grafih z omejenimi velikostmi negativnih uteži. Nato pa s pristopom skaliranja uteži predstavi omenjeni algoritem, dokaže njegovo pravilnost in utemelji časovno zahtevnost.20232023-09-07 11:50:00Diplomsko delo/naloga149572sl