Minimize sum of all pair shortest paths after adding one extra edge between 2 nodes

I don’t have access to this problem anymore so I was hoping if anyone could confirm if my approach is correct, or if wrong what would be correct approach.

Problem statement:
Given a graph with n nodes and m edges, print the sum of minimum cost paths between every possible node pairs. Cost of a path is the number of edges in that path. You are allowed to add an edge between any 2 nodes. The graph is guaranteed to be complete and there are no duplicate edges.

Constraints (IIRC): 0 < n <= 50

The approach that I had thought of was to first use ford-fulkerson to find min cost between node pairs in O(n^3) time. There should be O(n^2) possible edges that can be added, so I thought of trying every edge one by one.
For a new edge added between 2 nodes u and v, I would set distance between them to 1, and then check distance of every pair of nodes from u and v that I got from ford-fulkerson.
If 1 + dist(node1, u) + dist(node2, v) is less than dist(node1, node2), I would update the distance.


1 Like