1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ So you are not looking for a direct answer here? $\endgroup$
    – xskxzr
    Apr 28 '18 at 15:44
  • $\begingroup$ @xskxzr No, I'm looking for a direct answer here. I apologize for not clarifying. (edited ) thank you. $\endgroup$
    – Abdulkader
    Apr 28 '18 at 17:26
  • $\begingroup$ This is called "dynamic shortest paths". $\endgroup$
    – D.W.
    Apr 28 '18 at 18:50
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 29 '18 at 6:07
  • $\begingroup$ @D.W. "dynamic shortest paths" was very useful suggestion, thank you again. $\endgroup$
    – Abdulkader
    Apr 29 '18 at 6:11
1
$\begingroup$

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

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

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.

$\endgroup$
1
  • $\begingroup$ (affecteffect, from $a$ to $z$ - or - between $x$ and $y$) $\endgroup$
    – greybeard
    May 9 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.