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).