9
$\begingroup$

I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network. An answer to my previous question led me to Hiroki Yanagisawa's paper "A multi-source label-correcting algorithm for the all-pairs shortest paths problem" [IPDPS 2010] which is performing really well.

But what about updates? I couldn't produce a technique which can update the shortest paths quickly when the weight of an edge changes. On researching, I came across a paper "On Dynamic Shortest Path problems", which states that

Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem.

So the question is: Are there useful heuristic approaches to solve this problem?

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ I think that it is unfair to say “On researching through many papers finally concluded with …” without acknowledging the answer you received in your previous question which gave the reference to exactly the same paper. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 30, 2012 at 17:14
  • $\begingroup$ The here link is to this question instead of the other. :-/ $\endgroup$
    – Michel de Ruiter
    Commented Jan 30, 2012 at 22:27
  • 3
    $\begingroup$ Edited for clarity and grammar; fixed broken link to previous answer. $\endgroup$
    – Jeffε
    Commented Jan 31, 2012 at 2:23
  • 3
    $\begingroup$ Perhaps this paper can help you: db.csail.mit.edu/pubs/cq_icde_cr.pdf $\endgroup$
    – Marzio De Biasi
    Commented Feb 1, 2012 at 13:16

2 Answers 2

Reset to default
1
$\begingroup$

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 & 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 & publishable result.)

Improve this answer
$\endgroup$
-1
$\begingroup$

And in what kinds of updates are you interested? Both weight increase and decrease? Obviously, it should not be hard to solve edge increases since such an update influences only those optimal paths containing the changed edge and it is not hard to recomputed them quickly (actually, it can be done even more efficiently). Weight decrease is harder case but it does not make sense in route planning practice (usually).

Anyway, if you are already using some route planning (all pairs shortest path) approach, you should look for its "dynamization". I would not consider heuristics since I am not aware of any good heuristic route planning algorithm.

So what kind of updates are we talking about?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hello,Thanks for the reply.By updates I mean, both the increase & decrease. Basically every road has a score, depending upon the traffic at that edge,the score can decrease and increase. So the algorithm needs to adapt so that it can provide the shortest path considering the updates in all the shortest paths it has already found rather than re-finding all pair shortest paths.Can you please explain/provide link for the update part, I mean how would it be effective for all pairs? Secondly from the second para, apart from all pairs shortest path approach, can there be any other effective approach $\endgroup$
    – Jatin
    Commented Feb 1, 2012 at 6:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.