Dynamic All Pairs Shortest Paths algorithm

Question

I heard about the following problem in a competitive programming camp:

Given an undirected weighted graph $G$ with one vertex initially.

Suppose you are given two types of queries:

1. Add a new vertex to $G$ with some undirected weighted edges between this vertex and subset of vertices added previously to $G$ in time complexity $O(n^2)$, where negative weights are allowed.

2. Find the length of the shortest path between two vertices in $O(1)$.

Note: Floyd Warshall's algorithm is $O(n^3)$ for each query of type 1.

I'm looking for (in addition to your answer):

• Any useful reference to solve such a problem.

• Links for similar problems in online judges (Codeforces, SPOJ .. etc).

Answer 1

You maintain a table $d$ where $d(i,j)$ represents the length of the shortest path from vertex $i$ to vertex $j$, so query 2 can be done in $O(1)$.

For query 1, when a new vertex $u$ is added, for each old vertex $v$, calculate the length of the shortest path from $u$ to $v$ by

$$d(u,v),d(v,u)\leftarrow\min_s(w(u,s)+d(s,v)).$$

where $s$ varies among all neighbors of $u$, and $w(u,s)$ represents the weight of edge $(u,s)$. This process takes $O(n^2)$. Now if there is no negative cycle, for each old vertex $v$, $d(u,v)$ and $d(v,u)$ correctly record the length of the shortest path from $u$ to $v$. It's also not hard to detect if there is a negative cycle.

Then, for any old vertices $s,t$, update $d(s,t)$ to

$$d(s,t)\leftarrow\min\{d(s,t),d(s,u)+d(u,t)\}.$$

This can also be done in $O(n^2)$.

Now after the two steps above, if there is no negative cycle, for each pair of vertices $x,y$, $d(x,y)$ correctly records the length of the shortest path from $x$ to $y$.

Answer 2

It called incremental all pairs shortest paths. Because you just add edges you don't have to deal with destroyed shortest paths but you only need to check if the added edge allows shorter paths. Notice that the affect is not local (i.e. after adding edge a shortest path between s to t might be replaced by a distinct path).

Suppose you add $e=(v,u)$. What you have to do is find with Bellman-Ford all shortest paths to $v$ and all shortest paths from $u$ (Bellman-Ford on reversed graph edges). Then for every $s, t \in V$ let $d_{G\cup e}(s, t)=\min(d_G(s,t), d_{G\cup e}(s, v)+w(e)+d_{G\cup e}{d(u, t)})$.

I hope this helps.