20.500.12556/RUL-149572 Najkrajše poti v grafih z negativnimi utežmi Shortest paths in graphs with negative weights V 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. The thesis focuses on the shortest path problem in graphs with negative weights. Bellman-Ford algorithm, one of the classical approaches for computing shortest paths in graphs with n vertices and m edges, can handle negative weights. Yet its time complexity O(mn) is significantly inferior to Dijkstra's algorithm, whose time complexity is near-linear O(m + n log n). Unfortunately Dijkstra's algorithm cannot handle negative weighted edges. In the thesis we present a randomized near-linear time algorithm for computing shortest paths in negatively weighted graph, whose time complexity is O(m p(log n + log W)), where p is a polynomial and W is the modulus of negative weights. The first such algorithm was found by Bernstein, Nanongkai and Wulff-Nielsen. Shortly after an improved result - both in presentation and in reduction of logarithmic factor - was found by Bringmann, Casiss and Fischer. We first present the idea of the algorithm and the approach on the class of graphs with very small negative weights. Later we use the scaling method to allow the solution of the general case. We establish both the correctness and the time complexity. najkrajše poti BNW algoritem dekompozicija grafov shortest paths BNW algorithm graph decomposition true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2023-09-07 11:50:00 2023-09-07 11:50:01 2023-11-20 10:42:24 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 36798 165541891 Komel_Vita_-_Najkrajse_poti_v_grafih_z_negativnimi_utezmi.pdf Komel_Vita_-_Najkrajse_poti_v_grafih_z_negativnimi_utezmi.pdf 1 6E099F42204B12443F66DCF1B9D751C7 6e794841b8476ae7441da0538707478103e939bdb436949cb4224dd11256bd0c e86b247d-4d63-11ee-9934-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=174056 Fakulteta za računalništvo in informatiko Fakulteta za matematiko in fiziko 0 0 0