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$
  • $\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$
  • $\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

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.