Improve total travel distance in a graph

user_10325838 0
Viewed 57

Recently in a coding test, I encountered a question based on graphs which I was unable to solve.

So in the question, we were given a road network (a weighted undirected graph), roads were represented by edges (and they had some weight) and cities were represented by vertices. Also we were given a list of proposed roads (i.e. 3 numbers, 2 end-points/cities it connected and other number was the weight) that can be added in the given road network. We had to tell which road upon adding to the network minimized the total travelling distance in the network. Total travelling distance was defined as the sum of the shortest path distances between all pairs of cities. Constraints:

No. of vertices: 100, No. of edges: 1000, No. of road proposals: 1000.

What would be the most efficient approach to solve this problem?

graph algorithm
1 Answers

Compute all-pairs shortest paths and store them in a matrix. (Floyd–Warshall is simple and works well on dense graphs; running Dijkstra from each vertex is also an option.)

For each edge uv that can be added, we can evaluate the updated distance between s and t as min(d(s, t), d(s, u) + ℓ(uv) + d(v, t), d(s, v) + ℓ(uv) + d(u, t)), where d denotes distance in the base graph, and ℓ(uv) is the length of uv.

Assuming Floyd–Warshall, this all takes time O(|V|³ + k |V|²) where k is the number of edges that can be added. This is surely fast enough under the given constraints.

user_21446690
Related