Finding the shortest paths from a single source in weighted graphs is a classic problem in the field of algorithms and data structures. This problem can be solved using Dijkstra's algorithm. However, in this thesis, we deal with a version of the problem in which the graph can be continuously updated. In particular, in each step, one of the edge weights can be modified, or an edge can be added or removed. Of course, we could run Dijkstra's algorithm after each update, but there are also more efficient approaches. In the thesis, we describe the so-called incremental and decremental algorithms; the former handles edge insertions and weight decreases, and the latter deals with edge removals and weight increases. We implemented both algorithms and tested them using different test scenarios.
|
