# Dynamic All Pairs Shortest Paths algorithm

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.

• Any useful reference to solve such a problem.

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

• So you are not looking for a direct answer here? – xskxzr Apr 28 '18 at 15:44
• @xskxzr No, I'm looking for a direct answer here. I apologize for not clarifying. (edited ) thank you. – Abdulkader Apr 28 '18 at 17:26
• This is called "dynamic shortest paths". – D.W. Apr 28 '18 at 18:50
• I am suggesting that you do some research on the dynamic shortest paths problem. I think you'll find a bunch of literature on the problem, with a variety of techniques for it. – D.W. Apr 29 '18 at 6:07
• @D.W. "dynamic shortest paths" was very useful suggestion, thank you again. – Abdulkader Apr 29 '18 at 6:11

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

• I think I understood this and here is my submission for a classical problem using this idea. Could you add, if possible, a recommended reference for more details about dynamic shortest paths, please? and thanks for your help. – Abdulkader May 2 '18 at 20:47
• @Abdulkader I came up with this algorithm by myself. I don't know any reference. – xskxzr May 3 '18 at 4:06