I have a planar(|E|=O(V)) undirected graph with positive edge weights.

I have already calculated all pairs shortest path with Floyd–Warshall algorithm.

Now I want to recalculate APSP with an edge removed. I'm not interested in the path and just having the distances is enough for me.

I want a highly parallelizable method and I only have one update so there is no need to support multiple edge removals.

Can I do this is something better than O(V^3)?

Edit: I also need to add edges but that could easily be implemented in O(V^2) via simple matrix addition(and thus be highly parallelizable).

Edit: My final goal is to construct |E| new graphs each with only one edge removed from the original graph, and then calculate APSP in a batched mode. In case you are wondering, I want this algorithm to compute a metric, related to APLS(but not APLS itself).

  • $\begingroup$ There are a number of papers on the topic of dynamic all-pairs shortest paths. However, usually you need to keep some additional data structures as you construct the initial graph and APSP solution, rather than just taking an arbitrary existing graph with known APSP. Is this a problem? $\endgroup$ – Aaron Rotenberg Dec 16 '19 at 11:47
  • $\begingroup$ @AaronRotenberg No, I'm totally fine with recalculating the initial APSP with another data structure. My main concern is the parallelizability of that data structure, I mean can it be used in a batch mode? $\endgroup$ – Separius Dec 16 '19 at 13:19
  • 1
    $\begingroup$ What does parallelizability mean in your context? You said you are only removing one edge per graph, so it's not multiple edge removals. Are you doing this on multiple graphs at once and need vectorizability across the graphs? If so, can you make any assumptions on shared properties of the graphs, e.g. same number of vertices? $\endgroup$ – Aaron Rotenberg Dec 16 '19 at 13:24
  • $\begingroup$ @AaronRotenberg yes I mean vectorizability across graphs with the same number of vertices(I have also updated my question(second Edit)) + that would be great if the algorithm itself is also matrix friendly, for example floyd-warshall is easy to implement with matrix addition of adjacency matrix. $\endgroup$ – Separius Dec 16 '19 at 13:28
  • 1
    $\begingroup$ The fact that you are doing this for each edge and the mention of APLS makes me think this question might be an XY problem situation. That is, your actual problem is how do I compute APLS efficiently, and there might be an asymptotically more efficient way of doing that than by going through $|E|$ iterations of a dynamic APSP algorithm. $\endgroup$ – Aaron Rotenberg Dec 16 '19 at 13:37

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.