2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented Jan 30, 2014 at 0:34
  • $\begingroup$ Have you looked into routing algorithms? They solve exactly this problem, and it's non-trivial. $\endgroup$
    – Raphael
    Commented Jan 30, 2014 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
    Commented Jan 30, 2014 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
    Commented Jan 30, 2014 at 13:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.