All dynamic algorithms mentioned perform better than
recomputation on certain inputs. Yet, none of them
has a worst-case complexity better than BA on all graphs since
all require an update of an APSP problem.
For this problem, no algorithm exists
which has better worst-case running time than recomputation [1]}. In addition, the problem of updating BC
seems even harder than the dynamic APSP problem. Indeed,
the dependencies (and therefore BC) might
need to be updated even on nodes whose distance from the source
has not changed, as they could be part of new shortest paths or not
be part of old shortest paths any more.
