DSAA

· · 个人记录

Introduce the algorithm

12112104 程司哲 Reading report for the SSSP paper

The classic algorithm for single-source shortest paths(SSSP) problem are Bellman-Ford and Dijkstra's algorithm. However, the Bellman-Ford Algorithm has the time complexity of O(mn), and Dijkstra's Algorithm returns wrong solution for graph which has negative-weight edges. This paper discusses a new algorithm which can process SSSP problem with negative edge weights in O(mlog^8(n)log(W)), which is non-linear, with a randomize way.

The algorithm use graph decomposition and elementary combinatorial tools instead of sophisticated continuous optimization methods and dynamic algorithm which all other recent developments used.

The key of the algorithm is graph decomposition. This algorithm decomposes any directed graph to many strongly-connected components, which make the sub-problerm in every part can be solved in non-linear time. Generally, the paper raised two important sub-algorithms: ScaleDown and SPmain. The purpose of ScaleDown is to decompose the graph, which make every part can be solved in Dijkstra's Algorithm. SPmain finds a shortest path tree in the base of ScaleDown. And support the conditions of graphs which contain a negative-weight cycle.

The paper also uses a way called low-diameter decomposition. This algorithm can decomposes any directed graph with non-negative edge weights into SCCs of small diameter. Finally, it uses all these tools and a way of deciding Price Function, to transfer the original graph into a graph which contains no negative weight edges, which can solved by Dijkstra's algorithm directly.

Price Functions

Price functions are useful tools for SSSP problems. Given G = (V, E, w) and a price function V \rightarrow Z， define w_p(u, v) = v(u, v) + \phi(u) - \phi(v), w0 denoted reduced weights.

Our goal is to find a w_0 which has non-negative weights.

The way: 1. Create a dummy source s with edges of weight 0 to every vertex.

  1. set \phi(v) = dist(s, v)

The paper proves a lemma: We can compute all dist(s, v) in time O(m, k), which s becomes a source and all shortest path from s contain at most k negative edges. (extends of Dijkstra)

Improved lemma: For the average vertex there are at most k negative edges(don't need every vertices!), we can also find such an algorithm.

So we can set a new goal: Reduce the negative edges as more as possible.

Then, we come to:

Low Diameter Decomposition

We want to make the connected components - E_{sup} have weak diameter <= D.

The tough procedure:

  1. Repeatedly pick an arbitary source and grow a ball for a randomly chosen threshold.

  2. Add all edges on the boundary of ball to E_sep

  3. Recurse onto other parts of G.

The algorithm splits edges into several kinds by the relationship of SCCs. Edges inside, between and edges of E_{sup}. Each phase will "fix" one class of edges, that is to make them non-negative. Type 2 is based on the character of DAGs, type 3 is based on E_{sup} is small and restricted by the weak diameter.

ScaleDown

The algorithm has several phases. In Phase 0, it decompose the whole graph into SCCs with weak diameter, which directly use the tool of Low Diameter Decomposition. In Phase 1, it trys to make edges inside the SCCs non-negative. We called ScaleDown recursively in this phase. In phase 2, it makes all edges between the SCCs non-negative, except the edge set in the small graph. And in last phase, we fix the edges of E_{sup}.

Input of the algorithm: graph G with w(e) >= -2B

Output: price function such that price >= -B.

In detail, we can find that we also handle 3 kinds of edges as we did in Low Diameter Decomposition.

SPMain

The function scales up all edge weights. Then, it creates an equivalent graph by scaling up edge weights by 2n. Then, it calls ScaleDown until we find a price function. Then we can prove that we made a new graph G* which has non-negative weights. Finally, we compute a shortest path tree from s using dijkstra.

Finally, we use a method called price function to prove the correctness of the algorithm.