4
$\begingroup$

Given

  • an undirected graph of $n$ nodes with weighted edges and
  • a sequence $S=((e,w),...)$ of updates, always decreasing, of the weight $w$ of edge $e$.

What is the online complexity of computing the shortest pair between each pair of nodes in the graph after each updates? Is there any solution better than solving the problem offline in time within $O(n^3)$ (using Floyd-Warshall's algorithm) after each update?

$\endgroup$
  • 1
    $\begingroup$ Can you define better the input of your problem, and give references to the solution you consider? In particular, the meaning of "Assume a situation where the edge weights can be reduced." is not clear. $\endgroup$ – Jeremy Aug 20 '13 at 13:19
  • $\begingroup$ let the cost of a edge at start(time $t_0$) is 10. now at $t_1$ the cost is 7, at $t_3$ cost is 8 and so on. I want to calculate the all pair shortest path at $t_n$ (n=0,1,2) $\endgroup$ – Debobroto Das Aug 20 '13 at 17:21
  • $\begingroup$ if the cost is 7 at time $t_1$ and 8 at time $t_3$, isn't it increasing rather than decreasing? $\endgroup$ – Jeremy Aug 22 '13 at 0:52
0
+50
$\begingroup$

I am not sure I understood well your question, but if all weights are positive, I think that you can support weights updates in time within $O(n)$ (better than $O(n^3)$ per update, which I understand is what you asked?). Consider

  • the symmetric matrix $W$ (as in Weight) which stores, for each pair $\{i,j\}$, the weight of this edge;
  • the symmetric matrix $T$ (as in Total) which stores, for each pair $\{i,j\}$, the total weight of the minimal path from $i$ to $j$; and
  • the symmetric matrix $N$ (as in Next) which stores, for each pair $\{i,j\}$, the first vertex $k$ of the shortest path from $i$ to $j$ (the entire path can then be extracted by checking $\{k,j\}$ recursively). If there are several minimal paths, take the first in lexicographical order if $i<j$ and the last in lexicographical order if $i>j$ to avoid forming cycles.

Initialize $N$ in time within $O(n^3)$ (or better via faster matrix multiplications algorithms). The values of $N$ form a spanning tree of at most $n$ edges and no shortest path contains twice the same edge.

Consider an update decreasing the weight of the edge $\{i,k\}$. For each entry $j$ of the row $i$ in $N$,

  • if $N\{i,j\}=k'\neq k$ and $W\{i,k'\}+T\{k',j\} > W\{i,k\}+T\{k,j\}$,

    • update $N\{i,j\}\leftarrow k$ and $T\{i,j\}\leftarrow W\{i,k\}+T\{k,j\}$;
    • update the other entries of $T$ by following the paths involving the edge $\{i,j\}$, using the symmetry of $N$.
  • Otherwise, do nothing:

    • if $N\{i,j\}=k$, given that the weight is decreasing, this particular path is still optimal and does not need to be updated;
    • if $N\{i,j\}=k'\neq k$ and $W\{i,k'\}+T\{k',j\} < W\{i,k\}+T\{k,j\}$, the decrease was not important enough to change the minimum path.

Given the spanning tree structure of the solution of the all pair minimum path and the fact that the weights are always decreased, I think that this gives linear time per update. I think you could easily get the same result for directed weighted graphs, at the cost of some extra space and a more complicated structure.

$\endgroup$
  • $\begingroup$ "The values of $N$ form a spanning tree ..." how? $\;$ $\endgroup$ – user6973 Aug 22 '13 at 5:16
  • $\begingroup$ Discussing on this after doing some simulation of my own. @Jeremy $\endgroup$ – Debobroto Das Aug 22 '13 at 5:31
  • $\begingroup$ @RickyDemer: I was assuming the unicity of minimal paths (then there cannot be any cycles, as it would imply two minimal paths). I corrected my solution to deal with non-unique minimal paths by giving an order between the paths. $\endgroup$ – Jeremy Aug 22 '13 at 9:54
  • $\begingroup$ @DebobrotoDas: ok. Did I understand correctly your question and did you agree with my reformulation? $\endgroup$ – Jeremy Aug 22 '13 at 9:55
  • $\begingroup$ @Jeremy: $\;\;$ That's quite independent of the point I was trying to make. $\:$ $N$ holds vertices, $\hspace{.46 in}$ not edges, and the set of $\{i,k\}$ edges induced by $N$ can have $n^2$ edges. $\:$ (For example, $\hspace{.6 in}$ that will happen for a complete graph whose edge weights are almost equal to each other.) $\hspace{.4 in}$ $\endgroup$ – user6973 Aug 22 '13 at 18:47

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.