How to maintain an adding a new edge to the graph and efficiently update Floyd-Warshall all-pairs distances? Floyd-Warshall algorithm uses distances matrix, how we can update it after adding a new edge to the graph?
We can rerun Floyd-Warshall Algorithm, and it will take O(V^3). Can we make it faster?
Let's say the edge goes from vertex v to vertex w and has cost c:
If the distance matrix already has a shorter path from v to w, then adding the edge has no effect, so there's nothing to do.
Otherwise, the new edge becomes the shortest path from v to w, so enter it into the distance matrix, and then, for every other pair of vertices a and b, see if it can be made shorter by using the new edge. From the distance matrix you can easily find the cost of a-v-w-b and a-w-v-b. Note that one a or b might by the same as v or w.
Since you have to check every pair of vertices, this takes O(V2) time.
