Search code examples
algorithmdata-structureschartsgraph-theoryfloyd-warshall

Adding an edge in Floyd-Warshall algorithm

Assume we have computed the all-pairs distance matrix in a graph using the Floyd-Warshall algorithm. How can we efficiently update this distance matrix when a new edge is added?

We can of course rerun the Floyd-Warshall algorithm, but that will take O(V3). Can we make it faster?

Solution

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