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.
|
