Problem statement
In the problem, you are given an undirected graph with ‘V’ vertices numbered from 1 to ‘V’ and ‘E’ edges between these ‘V’ vertices also you are given with an array named as operation of ‘K’ size which store ‘K’ number of vertices and you are allowed to join an edge between any two vertices given in the array and by making these connections. Your task is to maximize the shortest path between the first and the last vertex.
Note: You may add an edge between any two selected vertices that have already an edge between them to maximize the shortest path.
Example
Input
An unweighted graph is given with 5 vertices named as 1, 2, 3, 4, 5, and 4 edges between (1-2),(2-3),(3-4), and (4-5). The value of K here is 3 and the operation array is given as {1, 2, 4}. We have to maximize the shortest path by adding a single edge between the combinations of all the possible vertices in the operation array.
So let’s explore all the possible combinations of vertices in the operation array
Considering edge 2, 4 from the operation array, the shortest distance between 1 and 5 here is 3
Considering the edge 1, 4 from the operation array, the shortest distance between 1 and 5 here is 2
Considering the edge 1, 2 from the operation array the shortest distance between 1 and 5 here is 4
Out of all these possible shortest distances, we have to maximize the shortest path or shortest distance. So the maximum of all the shortest distance that is max(2, 3, 4) is 4 so the answer for this graph is 4 units
Approach
This problem of maximize the shortest path can be solved in the series of steps as follows :
- The idea here is to calculate the minimum distance for every vertex from the first and the last vertex
- Let the shortest distance for a random vertex v from first node be xv and from the last vertex be yv
- To calculate the minimum distance from a source vertex to another vertex we can use breadth-first algorithm or Dijkstra’s algorithm
- For this, maintain a 2D matrix having 2 rows and v columns to store the minimum distance of all the vertices from the starting vertex in the first row and from the last vertex in the second row
- Now, choose two operation vertices a and b from operation[] array to minimize the value of min(xa + yb, ya + xb)
- Let distance = min(xa + yb, ya + xb)
- Fro minimizing this distance follow these rules
- Create a vector of pairs and store the value of (xv - yv) with their respective selected vertex and after storing all the values sort the vector of pairs
- Before traversing in the vector initialize the value of best to 0 and max to -INF
- Now traverse the above vector of pairs and for each selected node(say n) update the value of best to maximum of (best, max + dist[1][n]) and update max to maximum of (max, dist[0][n]).
- After the above operations the maximum of (dist[0][v-1] and best + 1) given the minimum shortest path which will ultimately solve the goal to maximize the shortest path