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

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

• So you are not looking for a direct answer here? Apr 28 '18 at 15:44
• @xskxzr No, I'm looking for a direct answer here. I apologize for not clarifying. (edited ) thank you. 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. Apr 29 '18 at 6:11

## 2 Answers

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. May 2 '18 at 20:47
• @Abdulkader I came up with this algorithm by myself. I don't know any reference. May 3 '18 at 4:06

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.

• (affecteffect, from $a$ to $z$ - or - between $x$ and $y$) May 9 at 10:01