Given a positive integer K and a weighted undirected connected graph of N nodes and E edges as an array Edges[] of the type {u, v, W} representing the edges between Node u and Node v having weight W, the task is to find the shortest distance between the two given nodes S and D after reducing the cost of at most K edges to 0.
Examples:
Input: N = 5, K = 1, Edges[][] = {{0, 1, 1}, {0, 4, 1}, {1, 2, 2}, {2, 3, 4}, {4, 3, 7}}, s = 0, d = 3
Output: 1
Explanation:
Below is the graph for the given test case:There are 2 possible routes between 0 and 3 viz. {0->1->2->3} and {0->4->3}
after reducing the distance of edge 4->3 to zero, the second route becomes 0->(4, 3) and hence the minimum distance is 1.Input: N = 5, K = 2, Edges[][] = {{0, 1, 2}, {0, 2, 3}, {2, 1, 2}, {2, 3, 1}, {3, 1, 2}, {3, 4, 3}, {4, 2, 4}}, s = 0, d = 3
Ouput: 2
Approach: The given problem can be solved using DFS Traversal and storing all possible paths between the two given nodes. Follow the steps below to solve the given problem:
- Initialize a variable, say minimumCost as INT_MAX that stores the resultant shortest distance.
- Traverse all paths from node S to node D in the graph using DFS Traversal and store all the edge weights from Node S to D obtained in a vector of vectors, say edgesPath[].
- After the above steps, sort each vector stored in edgesPath[] in decreasing order.
- Traverse the vector of vectors edgesPath[] for each vector, say A[], perform the following steps:
- Find the sum of the first K largest edges in A[].
- Update the value of minimiumCost to the minimum of the current (totalSum – sum) and mininmumCost.
- After completing the above steps, print the value of minimumCost as the result.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to get all the possible // paths from the source to destination void dfs_all( int n, int s, int d, vector<vector<pair< int , int > > >& graph, vector< bool >& vis, vector<vector< int > >& edge_path, vector< int >& temp_edge) { // One possible path, reached node D if (s == d) { edge_path.push_back(temp_edge); return ; } // Mark node s as visited vis[s] = true ; // Calculate number of edges with // node s as connection int edges_in_a = graph[s].size(); // Traverse all the connections // of node s for ( int i = 0; i < edges_in_a; i++) { // If the connected node // isn't visited if (!vis[graph[s][i].first]) { // Push back edge value // in temp_edge temp_edge.push_back(graph[s][i].second); // Call DFS function recursively dfs_all(n, graph[s][i].first, d, graph, vis, edge_path, temp_edge); // Pop back last added edge temp_edge.pop_back(); } } // Mark s as unvisited for more // possible paths vis[s] = false ; } // Function to find the minimum sum of // edges from source to destination // after reducing at most K cost to 0 int getDistance(vector<vector< int > >& edge_path, int k) { // Store the shortestDistance int shortestDistance = INT_MAX; // If edge_path vector is empty, // means no path exist if (edge_path.empty()) return -1; // Traverse all the vector in // the edge_path for ( auto x : edge_path) { // Base Case if (k == x.size()) return 0; // lets sort the vector in // decreasing order sort(x.begin(), x.end(), greater< int >()); // Find the sum of all the nodes int sum = 0; // Find the sum of k largest nodes int ksum = 0; for ( int i = 0; i < x.size(); i++) { sum += x[i]; if (i < k) ksum += x[i]; } // If the given shortestDistance // is shortest, then update the // shortestDistance shortestDistance = min(sum - ksum, shortestDistance); } // Return the shortestDistance return shortestDistance; } // Function to find the minimum sum of // weight of edges among all paths from // source to destination after reducing // at most K cost to 0 int solve(vector<vector<pair< int , int > > > graph, int n, int k, int src, int dest) { // Stores all the vectors of edges for // every path traversed in DFS call vector<vector< int > > edge_path; // Store the edges of particular path vector< int > temp_edge; // Boolean visited vector vector< bool > vis(n, false ); // DFS Call dfs_all(n, src, dest, graph, vis, edge_path, temp_edge); return getDistance(edge_path, k); } // Driver Code int main() { int n = 5, e = 5, k = 1; vector<vector<pair< int , int > > > graph(n); // Given Adjacency List graph[0].push_back(make_pair(1, 1)); graph[1].push_back(make_pair(0, 1)); graph[0].push_back(make_pair(4, 1)); graph[4].push_back(make_pair(0, 1)); graph[1].push_back(make_pair(2, 2)); graph[2].push_back(make_pair(1, 2)); graph[2].push_back(make_pair(3, 4)); graph[3].push_back(make_pair(2, 4)); graph[4].push_back(make_pair(3, 7)); graph[3].push_back(make_pair(4, 7)); int a = 0, b = 3; cout << solve(graph, n, k, a, b); return 0; } |
Java
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; class Main { // Function to get all the possible // paths from the source to destination static void dfsAll( int n, int s, int d, List<List<Pair>> graph, boolean [] vis, List<List<Integer>> edgePath, List<Integer> tempEdge) { // One possible path, reached node D if (s == d) { edgePath.add( new ArrayList<>(tempEdge)); return ; } // Mark node s as visited vis[s] = true ; // Calculate the number of edges with // node s as a connection int edgesInA = graph.get(s).size(); // Traverse all the connections // of node s for ( int i = 0 ; i < edgesInA; i++) { // If the connected node // isn't visited if (!vis[graph.get(s).get(i).first]) { // Push back edge value // in tempEdge tempEdge.add(graph.get(s).get(i).second); // Call DFS function recursively dfsAll(n, graph.get(s).get(i).first, d, graph, vis, edgePath, tempEdge); // Pop back the last added edge tempEdge.remove(tempEdge.size() - 1 ); } } // Mark s as unvisited for more // possible paths vis[s] = false ; } // Function to find the minimum sum of // edges from source to destination // after reducing at most K cost to 0 static int getDistance(List<List<Integer>> edgePath, int k) { // Store the shortestDistance int shortestDistance = Integer.MAX_VALUE; // If edgePath list is empty, // means no path exists if (edgePath.isEmpty()) { return - 1 ; } // Traverse all the vectors in // the edgePath list for (List<Integer> x : edgePath) { // Base Case if (k == x.size()) { return 0 ; } // Sort the list in decreasing order Collections.sort(x, Comparator.reverseOrder()); // Find the sum of all the nodes int sum = 0 ; // Find the sum of k largest nodes int kSum = 0 ; for ( int i = 0 ; i < x.size(); i++) { sum += x.get(i); if (i < k) { kSum += x.get(i); } } // If the given shortestDistance // is shorter, then update the // shortestDistance shortestDistance = Math.min(sum - kSum, shortestDistance); } // Return the shortestDistance return shortestDistance; } // Function to find the minimum sum of // weight of edges among all paths from // source to destination after reducing // at most K cost to 0 static int solve(List<List<Pair>> graph, int n, int k, int src, int dest) { // Stores all the vectors of edges for // every path traversed in DFS call List<List<Integer>> edgePath = new ArrayList<>(); // Store the edges of a particular path List<Integer> tempEdge = new ArrayList<>(); // Boolean visited vector boolean [] vis = new boolean [n]; // DFS Call dfsAll(n, src, dest, graph, vis, edgePath, tempEdge); return getDistance(edgePath, k); } public static void main(String[] args) { int n = 5 , e = 5 , k = 1 ; List<List<Pair>> graph = new ArrayList<>(); // Given Adjacency List for ( int i = 0 ; i < n; i++) { graph.add( new ArrayList<>()); } graph.get( 0 ).add( new Pair( 1 , 1 )); graph.get( 1 ).add( new Pair( 0 , 1 )); graph.get( 0 ).add( new Pair( 4 , 1 )); graph.get( 4 ).add( new Pair( 0 , 1 )); graph.get( 1 ).add( new Pair( 2 , 2 )); graph.get( 2 ).add( new Pair( 1 , 2 )); graph.get( 2 ).add( new Pair( 3 , 4 )); graph.get( 3 ).add( new Pair( 2 , 4 )); graph.get( 4 ).add( new Pair( 3 , 7 )); graph.get( 3 ).add( new Pair( 4 , 7 )); int a = 0 , b = 3 ; System.out.println(solve(graph, n, k, a, b)); } } class Pair { int first, second; Pair( int first, int second) { this .first = first; this .second = second; } } |
Python3
# Python program of the above approach # Function to get all the possible # paths from the source to destination def dfs_all(n, s, d, graph, vis, edge_path, temp_edge): # One possible path, reached node D if s = = d: edge_path.append(temp_edge) return # Mark node s as visited vis[s] = True # Calculate number of edges with # node s as connection edges_in_a = len (graph[s]) # Traverse all the connections # of node s for i in range (edges_in_a): # If the connected node # isn't visited if not vis[graph[s][i][ 0 ]]: # Push back edge value # in temp_edge temp_edge.append(graph[s][i][ 1 ]) # Call DFS function recursively dfs_all(n, graph[s][i][ 0 ], d, graph, vis, edge_path, temp_edge) # Pop back last added edge temp_edge.pop() # Mark s as unvisited for more # possible paths vis[s] = False # Function to find the minimum sum of # edges from source to destination # after reducing at most K cost to 0 def getDistance(edge_path, k): # Store the shortestDistance shortestDistance = float ( 'inf' ) # If edge_path vector is empty, # means no path exist if not edge_path: return - 1 # Traverse all the vector in # the edge_path for x in edge_path: # Base Case if k = = len (x): return 0 # lets sort the vector in # decreasing order x.sort(reverse = True ) # Find the sum of all the nodes sum = 1 # Find the sum of k largest nodes ksum = 0 for i in range ( len (x)): sum + = x[i] if i < k: ksum + = x[i] # If the given shortestDistance # is shortest, then update the # shortestDistance shortestDistance = min ( sum - ksum, shortestDistance) # Return the shortestDistance return shortestDistance # Function to find the minimum sum of # weight of edges among all paths from # source to destination after reducing # at most K cost to 0 def solve(graph, n, k, src, dest): # Stores all the vectors of edges for # every path traversed in DFS call edge_path = [] # Store the edges of particular path temp_edge = [] # Boolean visited vector vis = [ False for _ in range (n)] # DFS Call dfs_all(n, src, dest, graph, vis, edge_path, temp_edge) return getDistance(edge_path, k) # Driver Code n = 5 e = 5 k = 1 graph = [[] for _ in range (n)] # Given Adjacency List graph[ 0 ].append([ 1 , 1 ]) graph[ 1 ].append(( 0 , 1 )) graph[ 0 ].append(( 4 , 1 )) graph[ 4 ].append(( 0 , 1 )) graph[ 1 ].append(( 2 , 1 )) graph[ 2 ].append(( 1 , 1 )) graph[ 1 ].append(( 3 , 3 )) graph[ 3 ].append(( 1 , 3 )) graph[ 2 ].append(( 4 , 1 )) graph[ 4 ].append(( 2 , 1 )) src = 0 dest = 4 print (solve(graph, n, k, src, dest)) |
C#
using System; using System.Collections.Generic; using System.Linq; class Graph { private List<List<Tuple< int , int > > > adjList; public Graph( int n) { adjList = new List<List<Tuple< int , int > > >(n); for ( int i = 0; i < n; i++) { adjList.Add( new List<Tuple< int , int > >()); } } public void AddEdge( int u, int v, int w) { adjList[u].Add(Tuple.Create(v, w)); } public List<List< int > > GetAllPaths( int s, int d) { var vis = new bool [adjList.Count]; var tempEdge = new List< int >(); var edgePaths = new List<List< int > >(); DFSAll(s, d, vis, edgePaths, tempEdge); return edgePaths; } private void DFSAll( int s, int d, bool [] vis, List<List< int > > edgePaths, List< int > tempEdge) { if (s == d) { edgePaths.Add( new List< int >(tempEdge)); return ; } vis[s] = true ; foreach ( var edge in adjList[s]) { if (!vis[edge.Item1]) { tempEdge.Add(edge.Item2); DFSAll(edge.Item1, d, vis, edgePaths, tempEdge); tempEdge.RemoveAt(tempEdge.Count - 1); } } vis[s] = false ; } public int GetMinimumSumOfEdges(List<List< int > > edgePaths, int k) { if (edgePaths.Count == 0) { return -1; } int shortestDistance = int .MaxValue; foreach ( var edgePath in edgePaths) { if (k == edgePath.Count) { return 0; } edgePath.Sort((a, b) = > b.CompareTo(a)); int sum = 0; int ksum = 0; for ( int i = 0; i < edgePath.Count; i++) { sum += edgePath[i]; if (i < k) { ksum += edgePath[i]; } } shortestDistance = Math.Min(shortestDistance, sum - ksum); } return shortestDistance; } public int Solve( int n, int k, int src, int dest) { var edgePaths = GetAllPaths(src, dest); return GetMinimumSumOfEdges(edgePaths, k); } } class Program { static void Main( string [] args) { int n = 5, e = 5, k = 1; var graph = new Graph(n); // Given Adjacency List graph.AddEdge(0, 1, 1); graph.AddEdge(1, 0, 1); graph.AddEdge(0, 4, 1); graph.AddEdge(4, 0, 1); graph.AddEdge(1, 2, 2); graph.AddEdge(2, 1, 2); graph.AddEdge(2, 3, 4); graph.AddEdge(3, 2, 4); graph.AddEdge(4, 3, 7); graph.AddEdge(3, 4, 7); int a = 0, b = 3; Console.WriteLine(graph.Solve(n, k, a, b)); } } // This code is contributed by Akash Jha |
Javascript
// Javascript Equivalent // Function to get all the possible // paths from the source to destination function dfs_all(n, s, d, graph, vis, edge_path, temp_edge){ // One possible path, reached node D if (s === d) { edge_path.push(temp_edge); return ; } // Mark node s as visited vis[s] = true ; // Calculate number of edges with // node s as connection let edges_in_a = graph[s].length; // Traverse all the connections // of node s for (let i = 0; i < edges_in_a; i++) { // If the connected node // isn't visited if (!vis[graph[s][i][0]]) { // Push back edge value // in temp_edge temp_edge.push(graph[s][i][1]); // Call DFS function recursively dfs_all(n, graph[s][i][0], d, graph, vis, edge_path, temp_edge); // Pop back last added edge temp_edge.pop(); } } // Mark s as unvisited for more // possible paths vis[s] = false ; } // Function to find the minimum sum of // edges from source to destination // after reducing at most K cost to 0 function getDistance(edge_path, k){ // Store the shortestDistance let shortestDistance = Infinity; // If edge_path vector is empty, // means no path exist if (edge_path.length === 0) { return -1; } // Traverse all the vector in // the edge_path for (let x of edge_path) { // Base Case if (k === x.length) { return 0; } // lets sort the vector in // decreasing order x.sort( function (a, b) { return b - a; }); // Find the sum of all the nodes let sum = 1; // Find the sum of k largest nodes let ksum = 0; for (let i = 0; i < x.length; i++) { sum += x[i]; if (i < k) { ksum += x[i]; } } // If the given shortestDistance // is shortest, then update the // shortestDistance shortestDistance = Math.min(sum - ksum, shortestDistance); } // Return the shortestDistance return shortestDistance; } // Function to find the minimum sum of // weight of edges among all paths from // source to destination after reducing // at most K cost to 0 function solve(graph, n, k, src, dest){ // Stores all the vectors of edges for // every path traversed in DFS call let edge_path = []; // Store the edges of particular path let temp_edge = []; // Boolean visited vector let vis = new Array(n).fill( false ); // DFS Call dfs_all(n, src, dest, graph, vis, edge_path, temp_edge); return getDistance(edge_path, k); } // Driver Code let n = 5; let e = 5; let k = 1; let graph = []; for (let i = 0; i < n; i++) { graph[i] = []; } // Given Adjacency List graph[0].push([1, 1]); graph[1].push([0, 1]); graph[0].push([4, 1]); graph[4].push([0, 1]); graph[1].push([2, 1]); graph[2].push([1, 1]); graph[1].push([3, 3]); graph[3].push([1, 3]); graph[2].push([4, 1]); graph[4].push([2, 1]); let src = 0; let dest = 4; console.log(solve(graph, n, k, src, dest)); |
1
Time Complexity: O((N*log N)NN)
Auxiliary Space: O(N2)
Efficient Approach: The above approach can also be optimized at the step where sorting is performed after finding all possible paths. Instead of sorting, the idea is to use MinHeap to calculate the sum of K largest weights in the graph to reduce the time complexity to O(N*log K) for that steps.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to get all the possible // paths from the source to destination void dfs_all( int n, int s, int d, vector<vector<pair< int , int > > >& graph, vector< bool >& vis, vector<vector< int > >& edge_path, vector< int >& temp_edge) { // One possible path, reached node D if (s == d) { edge_path.push_back(temp_edge); return ; } // Mark node s as visited vis[s] = true ; // Calculate number of edges with // node s as connection int edges_in_a = graph[s].size(); // Traverse all the connections // of node s for ( int i = 0; i < edges_in_a; i++) { // If the connected node // isn't visited if (!vis[graph[s][i].first]) { // Push back edge value // in temp_edge temp_edge.push_back( graph[s][i].second); // Call DFS function recursively dfs_all(n, graph[s][i].first, d, graph, vis, edge_path, temp_edge); // Pop back last added edge temp_edge.pop_back(); } } // Mark s as unvisited for more // possible paths vis[s] = false ; } // Function to find the minimum sum of // edges from source to destination // after reducing at most K cost to 0 int getDistance( vector<vector< int > >& edge_path, int k) { int shortestDistance = INT_MAX; // If edge_path vector is empty, // means no path exist if (edge_path.empty()) return -1; // Traverse all the vector in // the edge_path for ( auto x : edge_path) { if (k == x.size()) return 0; // Use heap to store the array priority_queue< int , vector< int >, greater< int > > minHeap; // Find the sum of all the nodes int sum = 0; // Find the sum of k largest nodes int ksum = 0; // Find the largest K edges using // minHeap for ( int i = 0; i < x.size(); i++) { sum += x[i]; ksum += x[i]; // Pushing edge in MinHeap minHeap.push(x[i]); // If heap size is K if (minHeap.size() > k) { ksum -= minHeap.top(); minHeap.pop(); } } // If the shortestDistance is // smallest, then update the // shortestDistance shortestDistance = min(sum - ksum, shortestDistance); } // Return the shortestDistance return shortestDistance; } // Function to find the minimum sum of // weight of edges among all paths from // source to destination after reducing // at most K cost to 0 int solve( vector<vector<pair< int , int > > > graph, int n, int k, int src, int dest) { // Stores all the vectors of edges for // every path traversed in DFS call vector<vector< int > > edge_path; // Store the edges of particular path vector< int > temp_edge; // Boolean visited vector vector< bool > vis(n, false ); // DFS Call dfs_all(n, src, dest, graph, vis, edge_path, temp_edge); return getDistance(edge_path, k); } // Driver Code int main() { int n = 5, e = 5, k = 1; vector<vector<pair< int , int > > > graph(n); // Given Adjacency List graph[0].push_back(make_pair(1, 1)); graph[1].push_back(make_pair(0, 1)); graph[0].push_back(make_pair(4, 1)); graph[4].push_back(make_pair(0, 1)); graph[1].push_back(make_pair(2, 2)); graph[2].push_back(make_pair(1, 2)); graph[2].push_back(make_pair(3, 4)); graph[3].push_back(make_pair(2, 4)); graph[4].push_back(make_pair(3, 7)); graph[3].push_back(make_pair(4, 7)); int a = 0, b = 3; cout << solve(graph, n, k, a, b); return 0; } |
Python3
# Python program of the above approach # Function to get all the possible # paths from the source to destination def dfs_all(n, s, d, graph, vis, edge_path, temp_edge): if s = = d: edge_path.append(temp_edge[:]) return vis[s] = True edges_in_a = len (graph[s]) for i in range (edges_in_a): if not vis[graph[s][i][ 0 ]]: temp_edge.append(graph[s][i][ 1 ]) dfs_all(n, graph[s][i][ 0 ], d, graph, vis, edge_path, temp_edge) temp_edge.pop() vis[s] = False # Function to find the minimum sum of # edges from source to destination # after reducing at most K cost to 0 def get_distance(edge_path, k): shortest_distance = float ( 'inf' ) if not edge_path: return - 1 for x in edge_path: if k = = len (x): return 0 # Use list to store the array min_heap = [] sum_val = 0 k_sum = 0 for i in range ( len (x)): sum_val + = x[i] k_sum + = x[i] min_heap.append(x[i]) # If list size is K if len (min_heap) > k: k_sum - = min_heap.pop(min_heap.index( min (min_heap))) shortest_distance = min (sum_val - k_sum, shortest_distance) return shortest_distance # Function to find the minimum sum of # weight of edges among all paths from # source to destination after reducing # at most K cost to 0 def solve(graph, n, k, src, dest): edge_path = [] temp_edge = [] vis = [ False ] * n dfs_all(n, src, dest, graph, vis, edge_path, temp_edge) return get_distance(edge_path, k) n, e, k = 5 , 5 , 1 graph = [[] for _ in range (n)] # Given Adjacency List graph[ 0 ].append(( 1 , 1 )) graph[ 1 ].append(( 0 , 1 )) graph[ 0 ].append(( 4 , 1 )) graph[ 4 ].append(( 0 , 1 )) graph[ 1 ].append(( 2 , 2 )) graph[ 2 ].append(( 1 , 2 )) graph[ 2 ].append(( 3 , 4 )) graph[ 3 ].append(( 2 , 4 )) graph[ 4 ].append(( 3 , 7 )) graph[ 3 ].append(( 4 , 7 )) a, b = 0 , 3 # Calling the solve function and printing the result print (solve(graph, n, k, a, b)) # this code is contributed by uttamdp_10 |
1
Time Complexity: O((N*log K)NN)
Auxiliary Space: O(N2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!