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(totalsumKsum, 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(totalWeightKsum, 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 N^{N} total possible path from source to destination, and each path can have at most N1 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^{ 2 }).
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(totalsumKsum, 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(totalWeightKsum, 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 N^{N} total possible path from source to destination, and each path can have at most N1 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^{ 2 }).
FAQs

What are Heaps?
The heap data structure is a special binary tree with two properties: a complete binary tree and a heaporder property.

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).

What are the applications of DFS?
Applications of DFS include cycle detection, topological ordering, finding strongly connected components of a graph, etc.

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. DFSbased 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!!