Edge-weight updates in all pair shortest path problem
your question seems quite advanced and it seems unlikely anyone has considered the incremental problem for the particular algorithm you are implementing when the new nonincremental algorithm was published by Yanagisawa as recently as 2010.

the algorithm you cite is apparently designed to be parallelizable therefore that seems like the 1st approach to optimizing it. ie implement it in a highly parallel implementation and just recompute all paths.

I have not seen a paper describing this, but how about this approach which seems to work in theory &amp; in general but details could be tricky (maybe it appears in a paper somewhere-- would be interested if anyone has seen a similar technique). every algorithm to solve the problem must basically reduce to a (2-way?) comparison of edge weights. the resulting paths are built out of the results of these comparisons. the "comparison tree" for every optimal path can be stored during the 1st computation of all pairs. 

then when any weights are changed, traverse through all prior stored/built-up comparison trees to recompute the answer. probably, for small changes, one would not have to descend "deeply" into those trees because the results of some or "many" prior comparisons are unchanged. one may have to modify the trees if new "comparison paths" in the trees are triggered but again this might not be expensive. however there would be a threshold where it is simpler to recompute everything from scratch when there are too many weight changes.

the main question of course is the memory cost of storing all the comparison trees.


(fineprint: and if all this actually worked, it would likely be a significant advance &amp; publishable result.)