1
$\begingroup$

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths.

An example is if we have vertices 1 to 5. We can see that initially, all of the paths are infinite except for the diagonal entries, i.e.:

  1 2 3 4 5
1 0 i i i i
2 i 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0

where i means "infinite". But if we add an edge (1, 2) then the 1-2nd and 2-1st entries of the table are updated:

  1 2 3 4 5
1 0 1 i i i
2 1 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0

Now, if we add the edge (2, 3), then obviously the 2-3rd and 3-2nd entires are updated, but also are 1-3rd and 3-1st (which has length 2, since the path is 1->2->3 and 3->2->1):

  1 2 3 4 5
1 0 1 2 i i
2 1 0 1 i i
3 2 1 0 i i
4 i i i 0 i
5 i i i i 0

Now, the more edges and vertices we add, the more complex the problem becomes, since we need to update other entries in the matrix if they are connected. The one fact that I know about this kind of graph is that it is symmetric along the diagonal.

I've been looking at this problem for a few hours and I do not think there is a generic algorithm that will solve the problem for a general unweighted, undirected graph. Are there resources on the problem?

Improve this question
$\endgroup$
8
  • $\begingroup$ The i-jth entry should be the length of the shortest path from vertex i to vertex j. Also, for any 2 vertices i and j, there exists at most 1 edge between them. The graph will be guaranteed to not be fully connected. $\endgroup$
    – Ryan Dougherty
    Jul 21, 2014 at 20:01
  • $\begingroup$ At most 1 edge. All I am looking for is an algorithm that will update a table similar to the one mentioned above. It will not add all possible edges, only edges that I give as input (i.e. I may only add O(n) edges whereas a fully connected graph has O(n^2) edges). $\endgroup$
    – Ryan Dougherty
    Jul 21, 2014 at 20:10
  • $\begingroup$ Sorry I had misread, I deleted the comments since they add nothing. $\endgroup$
    – lPlant
    Jul 21, 2014 at 20:16
  • $\begingroup$ No worries! :-) $\endgroup$
    – Ryan Dougherty
    Jul 21, 2014 at 20:19
  • $\begingroup$ What research have you done? There's been tons of work on dynamic shortest-path algorithms. You've found the right keywords; the word "dynamic" is indeed the critical word. So what research and searching have you done? You should be able to find plenty of work on this subject. For instance, Wikipedia links to citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.9856. Searching on this site and on CSTheory.SE immediately turns up cs.stackexchange.com/q/7250/755 and cs.stackexchange.com/q/1521/755 and cstheory.stackexchange.com/q/9990/5038. $\endgroup$
    – D.W. ♦
    Jul 21, 2014 at 22:34

1 Answer 1

Reset to default
3
$\begingroup$

The paper A New Approach to Dynamic All Pairs Shortest Paths by Camil Demetrescu and Giuseppe F. Italiano gives a solution to the directed version of the problem.

It involves saving two priority queues at each position on the matrix and updating and extracting information from these queues as edges are added. The psuedocode for the algorithm is on page 9 of the link.

For undirected graphs like this one, you could add 2 edges for each edge, one in each direction. This will not affect the time complexity of the algorithm.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the papers! For both, the graphs used are directed. Is there a (non-approximate) result for undirected graphs? $\endgroup$
    – Ryan Dougherty
    Jul 21, 2014 at 20:30
  • 2
    $\begingroup$ Could you outline the algorithm you cite and give a proper reference? That would make your answer more informative and more robust against link rot. $\endgroup$
    – Raphael ♦
    Jul 21, 2014 at 20:38
  • $\begingroup$ Thank you. What about for unweighted graphs? $\endgroup$
    – Ryan Dougherty
    Jul 21, 2014 at 21:37
  • $\begingroup$ @Ryan, This answer gives a reasonable algorithm for undirected graphs. There's nothing approximate about it. $\endgroup$
    – D.W. ♦
    Jul 21, 2014 at 22:34
  • $\begingroup$ @D.W. The approximate part was due to research on the dynamic APSP problem (almost all of the results were "approximate" in the title). $\endgroup$
    – Ryan Dougherty
    Jul 22, 2014 at 14:25

Your Answer

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

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