Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
INPUT 
2.2.
OUTPUT
2.3.
Explanation
2.4.
INPUT 
2.5.
OUTPUT
2.6.
Explanation
3.
Approach 1
3.1.
Algorithm
3.2.
Program
3.3.
INPUT
3.4.
OUTPUT
3.5.
Time Complexity
3.6.
Space Complexity
4.
Approach 2 (optimized)
4.1.
Algorithm
4.2.
Program
4.3.
INPUT
4.4.
OUTPUT
4.5.
Time Complexity
4.6.
Space Complexity
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Shortest Distance Between Given Nodes in a Bidirectional Weighted Graph by Removing any K Edges

Author Anant Dhakad
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this blog, we will discuss a problem based on DFS Algorithm. DFS in graphs is a widely asked topic in coding contests and technical interviews. There are many applications of DFS such as cycle detection, checking for bipartite graphs, finding all paths between two nodes. This blog will use DFS for finding all paths between two nodes.

Problem Statement

Ninja has been given a weighted undirected graph of N nodes and E edges and a positive integer K.

Your task is to find the shortest distance between source and destination node after reducing the weights of K edges to zero at most.

INPUT 

N = 5, E = 5 and K = 1

Edges: [(0, 1, 1), (0, 4, 1), (1, 2, 2), (2, 3, 4),  (4, 3, 7)]

Source = 0 and Destination = 3

OUTPUT

1

Explanation

There are two possible paths between 0 and 3. They are {0->1->2->3} and {0->4->3}. We can reduce the edge of 4->3 to zero in the second. So the total weight of the second path becomes one which is also the minimum distance.

INPUT 

N = 5, E = 7 and K = 2

Edges: [(0, 1, 2), (0, 2, 3), (2, 1, 2), (2, 3, 1), (3, 1, 2), (3, 4, 3), (4, 2, 4)]

Source = 0 and Destination = 3

OUTPUT

0

Explanation

The path with minimum distance after reducing two of its edges to zero is {0->2->3}.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1

We can solve this problem by using DFS traversal to store all paths from source to destination and then choosing the path with minimum distance (after reducing K largest edges to Zero).

Algorithm

1. We store edge weights of all paths from source to destination using DFS traversal in a vector of vectors ( named as all_paths ).

2. Iterate over vectors of all_paths. For each vector in all_paths, say path[ ], do the following steps:

  • Sort path[ ] in descending order.
  • Store the sum of the first K largest edges. Let’s call it Ksum.
  • Update minDist as min(totalsum-Ksum, minDist).

3. Return the value of minDist.

Program

#include <bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
 
// To store given graph.
vector<vector<pair<int,int>>> graph;
 
// To keep track of visited nodes.
vector<bool> vis;
 
// To store all the edges for every path traversed during the DFS call.
vector<vector<int>> all_paths;
 
// n - number of nodes in the graph.
int n;
 
// e - number of edges in the graph.
int e;
 
// k - number of edges whose weight can be reduced to zero.
int k;
 
/**
 * @brief DFS to find all possible paths from source to destination nodes.
 *
 * @param src Source Node.
 * @param dest Destination Node.
 * @param temp_path vector to store edge weights of the current path
 */
void DFS_findallpath(int src, int dest, vector<int> &temp_path){
 
    // Reached to destination that means we found
    // a path.
    if(src == dest){
        all_paths.push_back(temp_path);
        return;
    }
 
    // Marking current node as visited.
    vis[src] = true;
 
    // Iterate over all connections of SRC node.
    for(auto p : graph[src]){
        int v = p.F, w = p.S;
 
        // If this node is node visited earlier.
        if(!vis[v]){
            // Push the weight of src-->v edge in current path.
            temp_path.push_back(w);
 
            // Calling DFS recursively.
            DFS_findallpath(v, dest, temp_path);
 
            // Pop the last added edge weight so as to
            // explore all paths.
            temp_path.pop_back();
        }
    }
 
    // Marking current node as Unvisited for exploring
    // more possible paths.
    vis[src] = false;
}
 
/**
 * @brief Get the Minimum Distance from source to destination
 * after reducing weights of at most K edges to zero.
 *
 * @return int
 */
int getMinimumDistance(){
    // To store the minimum distance.
    int minDist = INT_MAX;
 
    // If all_paths is empty,
    // i.e. no path exists btw src and dest
    if(all_paths.size() == 0){
        return -1;
    }
 
    /**
     * @brief Iterate over all stored path to
     * find the minimum distance path.
     */
    for(auto path: all_paths){
       
        // If some path has less than equal to K edges
        // we can reduce them all to Zero.
        if(path.size() <= k){
            return 0;
        }
 
        // Sorting the edge weights in decreasing order.
        sort(path.rbegin(), path.rend());
 
        int totalWeight=0, Ksum=0;
        for(int i=0; i<path.size(); i++){
            totalWeight += path[i];
            if(i < k)Ksum += path[i];
        }
 
        // Update the minimum weighted path.
        minDist = min(totalWeight-Ksum, minDist);
    }
    return minDist;
}
 
void solve(){
    cin >> n >> e >> k;
    graph.resize(n);
    vis.resize(n, false);
 
    for(int i=0; i<e; i++){
        int u,v,w; cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
 
    /* Source and destination nodes. */
    int A, B; cin >> A >> B;
 
    // For storing the edge of a particular path.
    vector<int> temp_path;
    DFS_findallpath(A, B, temp_path);
 
    cout << "Minimum distance btw "<< A << " & " << B << " is: " << getMinimumDistance() << endl;
 
    graph.clear();
    vis.clear();
    all_paths.clear();
}
 
int main(){
    int tt;cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
}

INPUT

2
5 5 1
0 1 1
0 4 1
1 2 2
4 3 7
3 2 4
0 3
5 7 2
0 1 2
1 3 2
1 2 2
0 2 3
2 3 1
3 4 3
2 4 4
0 3

OUTPUT

Minimum distance btw 0 & 3 is: 1
Minimum distance btw 0 & 3 is: 0

Time Complexity

In the worst case, there can be NN total possible path from source to destination, and each path can have at most N-1 edges. We are using sorting to find the minimum distance path. So the time complexity of the above program is O( (N*logN)*N N ). 

Space Complexity

The auxiliary space complexity of the program is O( N)

Approach 2 (optimized)

We can optimize the above approach by efficiently finding the sum of K largest edges. Minheap can be used for finding the sum of K largest edges to reduce the time complexity of that from O(N*logN) to O(N*logK).

Algorithm

1. We store edge weights of all paths from source to destination using DFS traversal in a vector of vectors ( named as all_paths ).

2. Iterate over vectors of all_paths. For each vector in all_paths, say path[ ], do the following steps:

  • Initialize an empty minHeap
  • Iterate over all edge weights in the current path and maintain a minHeap of size K. 
  • Keep storing the sum of edge weight in totalsum and Ksum.
  • If the size of minHeap becomes greater than K, then pop the top element from the minHeap and subtract it from Ksum.
  • After the iteration is completed, we will get the sum of K largest edges in Ksum.
  • Update minDist as min(totalsum-Ksum, minDist).

3. Return the value of minDist.

Program

#include <bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
 
// To store given graph.
vector<vector<pair<int,int>>> graph;
 
// To keep track of visited nodes.
vector<bool> vis;
 
// To store all the edges for every path traversed during the DFS call.
vector<vector<int>> all_paths;
 
// n - number of nodes in the graph.
int n;
 
// e - number of edges in the graph.
int e;
 
// k - number of edges whose weight can be reduced to zero.
int k;
 
/**
 * @brief DFS to find all possible paths from source to destination nodes.
 *
 * @param src Source Node.
 * @param dest Destination Node.
 * @param temp_path vector to store edge weights of the current path
 */
void DFS_findallpath(int src, int dest, vector<int> &temp_path){
 
    // Reached to destination that means we found
    // a path.
    if(src == dest){
        all_paths.push_back(temp_path);
        return;
    }
 
    // Marking current node as visited.
    vis[src] = true;
 
    // Iterate over all connections of SRC node.
    for(auto p : graph[src]){
        int v = p.F, w = p.S;
 
        // If this node is node visited earlier.
        if(!vis[v]){
            // Push the weight of src-->v edge in current path.
            temp_path.push_back(w);
 
            // Calling DFS recursively.
            DFS_findallpath(v, dest, temp_path);
 
            // Pop the last added edge weight so as to
            // explore all paths.
            temp_path.pop_back();
        }
    }
 
    // Marking current node as Unvisited for exploring
    // more possible paths.
    vis[src] = false;
}
 
/**
 * @brief Get the Minimum Distance from source to destination
 * after reducing weights of at most K edges to zero.
 *
 * @return int
 */
int getMinimumDistance(){
    // To store the minimum distance.
    int minDist = INT_MAX;
 
    // If all_paths is empty,
    // i.e. no path exists btw src and dest
    if(all_paths.size() == 0){
        return -1;
    }
 
    /**
     * @brief Iterate over all stored path to
     * find the minimum distance path.
     */
    for(auto path: all_paths){
       
        // If some path has less than equal to K edges
        // we can reduce them all to Zero.
        if(path.size() <= k){
            return 0;
        }
 
        // Using heap to find minimum distance path.
        priority_queue<int, vector<int>, greater<int>>minHeap;
 
        // To store sum of all edges
        int totalWeight=0;
 
        // To store the sum of largest K edges
        int Ksum=0;
 
        for(int i=0; i<path.size(); i++){
            totalWeight += path[i];
            Ksum += path[i];
 
            minHeap.push(path[i]);
 
            // If heap size is more than K
            if(minHeap.size() > k){
                Ksum -= minHeap.top();
                minHeap.pop();
            }
        }
 
        // Update the minimum weighted path.
        minDist = min(totalWeight-Ksum, minDist);
    }
    return minDist;
}
 
void solve(){
    cin >> n >> e >> k;
    graph.resize(n);
    vis.resize(n, false);
 
    for(int i=0; i<e; i++){
        int u,v,w; cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
 
    /* Source and destination nodes. */
    int A, B; cin >> A >> B;
 
    // For storing the edge of a particular path.
    vector<int> temp_path;
    DFS_findallpath(A, B, temp_path);
 
    cout << "Minimum distance btw "<< A << " & " << B << " is: " << getMinimumDistance() << endl;
 
    graph.clear();
    vis.clear();
    all_paths.clear();
}
 
int main(){
    int tt;cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
}

INPUT

2
5 5 1
0 1 1
0 4 1
1 2 2
4 3 7
3 2 4
0 3
5 7 2
0 1 2
1 3 2
1 2 2
0 2 3
2 3 1
3 4 3
2 4 4
0 3

OUTPUT

Minimum distance btw 0 & 3 is: 1
Minimum distance btw 0 & 3 is: 0

Time Complexity

In the worst case, there can be NN total possible path from source to destination, and each path can have at most N-1 edges. We are using minHeap to find the minimum distance path. So the time complexity of the above program is O( (N*logK)*N N ). 

Space Complexity

The auxiliary space complexity of the program is O( N).

FAQs

  1. What are Heaps?
    The heap data structure is a special binary tree with two properties: a complete binary tree and a heap-order property.
     
  2. What is the time complexity of insertion and deletion in a Heap?
    The time complexity of insertion and deletion in a Heap containing N elements is O(logN).
     
  3. What are the applications of DFS?
    Applications of DFS include cycle detection, topological ordering, finding strongly connected components of a graph, etc.
     
  4. What is the time complexity of DFS traversal when performed using adjacency list representation of the graph?
    The time complexity of DFS on a graph with V vertices and E edges is O(V+E).

Key Takeaways

Cheers if you reached here!! 

This article aimed to discuss an intriguing problem using DFS traversal and heap. DFS-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!

Previous article
Solving Water Jug Problem using BFS
Next article
Multi Source Shortest Path in Unweighted Graph
Live masterclass