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