Maximize the shortest path between given vertices by adding a single edge

Code:

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
int v,e;
 
// To store graph as adjacency list
vector<int> graph[100000];
 
// To store the shortest path from first vertex and last vertex 
int dist[2][100000];
 
 
// Bfs traversal of finding shortest distance from source vertex
void bfs(int* dist, int starting_vertex)
{
    
    int queue[200000];
 
    // Filling initially each distance as infinity 
    fill(dist, dist + v, INF);
 
    int first = 0, second = 0;
    queue[first++] = starting_vertex;
    dist[starting_vertex] = 0;
 
    // Performing BFS 
    while (second < first) {
 
        int x = queue[second++];
 
        for (int y : graph[x]) {
            if (dist[y] == INF) {
 
                // Updating the distance and queue 
                dist[y] = dist[x] + 1;
                queue[first++] = y;
            }
        }
    }
}
 
/* 
    Function that maximise the shortest path between source and destination 
    vertex by adding a single edge between given selected nodes
*/
 
void shortestPathCost(int operation[], int K)
{
    vector<pair<int, int> > dp;
 
    // To update the shortest distance between node 1 to other vertices 
    bfs(dist[0], 0);
 
    // To update the shortest distance between node N to other vertices 
    bfs(dist[1], v - 1);
 
    for (int i = 0; i < K; i++) {
 
        
        // Storing the values  of (x[i] - y[i]) 
        dp.push_back({dist[0][operation[i]]
                            - dist[1][operation[i]],
                        operation[i]});
    }
 
    
    sort(dp.begin(), dp.end());
    int best = 0;
    int MAX = -INF;
 
    // Traversing  dp array 
    for (auto it : dp) {
        int a = it.second;
        best = max(best,
                MAX + dist[1][a]);
 
        /* 
             Maximise the value of (x[a] - y[b]) if a and b 
             are the current vertices in operations 
       */
        MAX= max(MAX, dist[0][a]);
    }
 
    // Printing the minimum cost
    cout<<min(dist[0][v - 1], best + 1);
 
}
 
int main()
{

    //Given total vertices and edges and operation array to choose edges 
    v = 5, e = 4;
    int K = 2;
    int operation[] = { 1, 2 ,4};
 
    // Sorting the nodes in operation
    sort(operation, operation + K);
 
    // Formation of graph
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(2);
    graph[3].push_back(4);
    graph[4].push_back(3);
 
    // maximise the shortest path

    shortestPathCost(operation, K);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

4 You can also try this code with Online C++ Compiler Run Code

Time Complexity 

The time complexity for the solution of “maximize the shortest path” will be O(V * log V + E)  where ‘V’ is the number of vertices and ‘E’ is the number of edges so let's understand the time complexity for the given problem.

First we have to sort the array operation that will cost us (K * log K ) for using inbuilt sort function 

Second we are entering in shortestPathCost function here we are calling bfs for first vertex which will cost us (V + E) and again for last vertex which will cost ( V + E ) so the time complexity for these 2 bfs calls will be 2 * ( V + E) and simultaneously we are also storing the shortest distance in the dp array of size V then we are sorting the dp array which will cost V * log V

So the total time complexity after all the operations will be:

 (K * log K ) + 2 * (V + E) + V * log V

Here K is very small compared with V so neglect the factor of K in the driver code now the complexiy will become 

2 * (V + E) + V * log V

            V * (log V + 2 ) + E

~  O(V * log V + E) 

Space Complexity 

The space complexity for the problem “maximize the shortest path” is O(N) since we are using a vector of pairs to store  (xv – yv)  here ‘xv’ is the shortest distance of a particular vertex ‘V’ from the first node and similarly ‘yv’ is shortest distance for the same vertex from the last node

Frequently Asked Questions

1. How Dijkstra is different from normal BFS?

Dijkstra and BFS are two different algorithms for calculating the shortest distance between two points. Dijkstra's approach is based on a priority queue, whereas regular bfs are based on a queue. we can use either of these algorithms to solve the above problem maximize the shortest path 

2. How to find the shortest path in the weighted graph?

There are two most famous algorithms for finding the shortest distance in the weighted graph that is using Bellman-Ford in O(VE). If there are no negative weight cycles we can also use the Dijkstra algorithm that will do the work for us in O(E + VLogV) 

3. Different ways to store graphs?

We can use an adjacency list, adjacency matrix, there is one more way here we can store Nodes as objects and edges as pointers.

Key Takeaways

In this blog, we solved the problem “maximize the shortest path” that is  maximizing the shortest distance between the first vertex and last vertex in the graph by adding a single edge from the operation array given.

Check out this problem - Root To Leaf Path

If you want to learn more about graphs and graph traversals and want to practice some questions which require you to take your basic knowledge on graphs a notch higher, then you can visit our Guided Path for graphs on  Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.