Najkrajše poti v grafih z negativnimi utežmi

diplomsko delo

Vita Komel (Author), Gašper Fijavž (Mentor)

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2023
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[V. Komel]
UDC:	004:519.17(043.2)
COBISS:	165541891
Views:	65
Downloads:	14
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Shortest paths in graphs with negative weights
Secondary abstract:	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.
Secondary keywords:	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;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	34 str.
ID:	19909012