<p>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 </p>

<ul>
<li>the symmetric matrix $W$ (as in Weight) which stores, for each pair $\{i,j\}$, the weight of this edge; </li>
<li>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 </li>
<li>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&lt;j$ and the last in lexicographical order if $i&gt;j$ to avoid forming cycles.</li>
</ul>

<p>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.</p>

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

<ul>
<li><p>if $N\{i,j\}=k'\neq k$ and $W\{i,k'\}+T\{k',j\} &gt; W\{i,k\}+T\{k,j\}$,    </p>

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

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

<p>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.</p>

CC BY-SA 3.0
2013-08-22T05:31:09.687Z
Discussing on this after doing some simulation of my own. @Jeremy
Debobroto Das
CC BY-SA 3.0
2013-08-22T09:54:59.373Z
@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.
J.y B.y
CC BY-SA 3.0
2013-08-22T09:55:43.567Z
@DebobrotoDas: ok. Did I understand correctly your question and did you agree with my reformulation?
J.y B.y
CC BY-SA 3.0
2013-08-23T15:00:09.510Z
@RickyDemer: Correct me if I am wrong, but the set of edges induced by $N$ cannot have $n^2$ distinct edges without creating cycles. If there is only one minimal path between each pair of nodes, $N$ implies at most $n$ distinct edges (albeit some repeated many times).  If there are more than one minimal path between some pair of nodes, ordering those paths so that to consider only one reduces again the graph described by $N$ to $n$ edges. Does this answer your comment?
J.y B.y
CC BY-SA 3.0
2013-08-23T19:28:24.677Z
@RickyDemer: would it imply a solution with updates in time within $O(n^2)$? Do you want to write this solution yourself?
J.y B.y
CC BY-SA 3.0
2013-08-23T19:29:16.433Z
@DebobrotoDas: RickyDemer might be correct and my solution incorrect. I will think more about it.
J.y B.y
CC BY-SA 3.0
2013-08-22T00:51:31.510Z
2013-08-22T09:51:24.297Z
2013-08-22T09:51:24.297Z
J.y B.y
<p>I think adding the keywords decremental/incremental might help you find the relevant papers. </p>

<p>See e.g. 
<a href="http://dx.doi.org/10.1007/978-0-387-30162-4_102" rel="nofollow">Camil Demetrescu, Giuseppe F. Italiano: Decremental All-Pairs Shortest Paths. Encyclopedia of Algorithms 2008</a> for an overview, <a href="http://dx.doi.org/10.1016/j.jcss.2005.05.005" rel="nofollow">Camil Demetrescu, Giuseppe F. Italiano: Fully dynamic all pairs shortest paths with real edge weights. J. Comput. Syst. Sci. 72(5): 813-837 (2006)</a>, and <a href="http://doi.acm.org/10.1145/1039488.1039492" rel="nofollow">Camil Demetrescu, Giuseppe F. Italiano: A new approach to dynamic all pairs shortest paths. J. ACM 51(6): 968-992 (2004)</a></p>

<p>Approximate versions have been considered as well; the most recent result I know of is <a href="http://arxiv.org/abs/1308.0776" rel="nofollow">Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai: Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization, FOCS 2013</a>.
Table 1 in their paper has an overview of results.</p>

CC BY-SA 3.0
2013-08-25T19:31:46.970Z
2013-08-25T19:37:56.437Z
2013-08-25T19:37:56.437Z
Christian Sommer
<p>Given </p>

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

<p>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?</p>

CC BY-SA 3.0
2013-08-20T13:19:13.613Z
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.
J.y B.y
CC BY-SA 3.0
2013-08-20T17:21:06.667Z
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)
Debobroto Das
CC BY-SA 3.0
2013-08-22T00:52:40.420Z
if the cost is 7 at time $t_1$ and 8 at time $t_3$, isn't it increasing rather than decreasing?
J.y B.y
<graph-algorithms>
Online version of All pair shortest path when path weights are updated
Debobroto Das
# Online version of All pair shortest path when path weights are updated

(Asked by: username_0 on 2013-08-17)

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?

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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)  
> **username_1**: if the cost is 7 at time $t_1$ and 8 at time $t_3$, isn't it increasing rather than decreasing?  

---

## 2 answers

### Answer by username_1 on 2013-08-22. Score: 0 | Accepted answer

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

> **Comments:**
> **username_0**: Discussing on this after doing some simulation of my own. @Jeremy  
> **username_1**: @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.  
> **username_1**: @DebobrotoDas: ok. Did I understand correctly your question and did you agree with my reformulation?  
> **username_1**: @RickyDemer: Correct me if I am wrong, but the set of edges induced by $N$ cannot have $n^2$ distinct edges without creating cycles. If there is only one minimal path between each pair of nodes, $N$ implies at most $n$ distinct edges (albeit some repeated many times).  If there are more than one minimal path between some pair of nodes, ordering those paths so that to consider only one reduces again the graph described by $N$ to $n$ edges. Does this answer your comment?  
> **username_1**: @RickyDemer: would it imply a solution with updates in time within $O(n^2)$? Do you want to write this solution yourself?  
> **username_1**: @DebobrotoDas: RickyDemer might be correct and my solution incorrect. I will think more about it.  

---

### Answer by username_2 on 2013-08-25. Score: 3

I think adding the keywords decremental/incremental might help you find the relevant papers.

See e.g.
[Camil Demetrescu, Giuseppe F. Italiano: Decremental All-Pairs Shortest Paths. Encyclopedia of Algorithms 2008](http://dx.doi.org/10.1007/978-0-387-30162-4_102) for an overview, [Camil Demetrescu, Giuseppe F. Italiano: Fully dynamic all pairs shortest paths with real edge weights. J. Comput. Syst. Sci. 72(5): 813-837 (2006)](http://dx.doi.org/10.1016/j.jcss.2005.05.005), and [Camil Demetrescu, Giuseppe F. Italiano: A new approach to dynamic all pairs shortest paths. J. ACM 51(6): 968-992 (2004)](http://doi.acm.org/10.1145/1039488.1039492)

Approximate versions have been considered as well; the most recent result I know of is [Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai: Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization, FOCS 2013](http://arxiv.org/abs/1308.0776).
Table 1 in their paper has an overview of results.


---

