diplomsko delo
Vita Komel (Avtor), Gašper Fijavž (Mentor)

Povzetek

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.

Ključne besede

najkrajše poti;BNW algoritem;dekompozicija grafov;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [V. Komel]
UDK: 004:519.17(043.2)
COBISS: 165541891 Povezava se bo odprla v novem oknu
Št. ogledov: 65
Št. prenosov: 14
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Shortest paths in graphs with negative weights
Sekundarni povzetek: 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.
Sekundarne ključne besede: shortest paths;BNW algorithm;graph decomposition;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Teorija grafov;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000407
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 34 str.
ID: 19909012
Priporočena dela:
, diplomsko delo
, diplomsko delo
, diplomsko delo