R - Heaps with Suspended Relaxation for Manipulating Priority Queues and a New Algorithm for Reweighting Graphs

This research is dedicated to two main problems in finding shortest paths in the graphs. The first problem is to find shortest paths from an origin to all other vertices in non-negatively weighted graph. The second problem is the same, except it is allowed that some edges are negative. This is a more difficult problem that can be solved by relatively complicated algorithms. We attack the first problem by introducing a new data structure - Relaxed Heaps that implements efficiently two main o...