I have a directed graph with $N$ vertices. Every pair of vertices is connected by two edges (one in each direction), and each of these edges has a weight which may be negative.

On various occasions 'edge update' operations occur, where the weight of an edge is modified (although the edge is never deleted, and no new edges or vertices are added). After each of these operations I wish to know the length of the shortest path between one 'root' vertex and every other vertex in the graph. I don't care what the path is, and I already know it must exist. I don't mind how negative weight cycles are handled.

I care about optimizing the running time of the single update operation and the $N$ queries that follow.

The obvious approach would be Bellman-Ford, which would take $O(|V||E|)$ which is $O(n^3)$.

Is there a faster way to do it?

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Have you tried searching the internet for dynamic single-source shortest path algorithms? $\endgroup$ – Yuval Filmus Jan 30 '14 at 0:34
  • $\begingroup$ Have you looked into routing algorithms? They solve exactly this problem, and it's non-trivial. $\endgroup$ – Raphael Jan 30 '14 at 11:01
  • $\begingroup$ @Raphael What kind of routing algorithm would you suggest? I'm aware it's non-trivial, but I was hoping at least an O(n^2) single-edge update would be possible. $\endgroup$ – jleahy Jan 30 '14 at 11:42
  • $\begingroup$ Remembered an older question on how many shortest paths may change when one edge is updated, but that one assumes APSPP. $\endgroup$ – Raphael Jan 30 '14 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.