Horje
Shortest distance between given nodes in a bidirectional weighted graph by removing any K edges

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:

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

Output

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;
}

Java

import java.util.*;
 
public class Main {
 
    // Function to get all the possible
    // paths from the source to destination
    static void dfs_all(int n, int s, int d,
                        ArrayList<ArrayList<Map.Entry<Integer, Integer>>> graph,
                        boolean[] vis,
                        ArrayList<ArrayList<Integer>> edge_path,
                        ArrayList<Integer> temp_edge) {
        // One possible path, reached node D
        if (s == d) {
            edge_path.add(new ArrayList<>(temp_edge));
            return;
        }
 
        // Mark node s as visited
        vis[s] = true;
 
        // Calculate the number of edges with
        // node s as a connection
        int edges_in_a = graph.get(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.get(s).get(i).getKey()]) {
 
                // Push back edge value
                // in temp_edge
                temp_edge.add(graph.get(s).get(i).getValue());
 
                // Call DFS function recursively
                dfs_all(n, graph.get(s).get(i).getKey(),
                        d, graph, vis,
                        edge_path, temp_edge);
 
                // Pop back the last added edge
                temp_edge.remove(temp_edge.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(
            ArrayList<ArrayList<Integer>> edge_path, int k) {
        int shortestDistance = Integer.MAX_VALUE;
 
        // If edge_path list is empty,
        // means no path exists
        if (edge_path.isEmpty())
            return -1;
 
        // Traverse all the lists in
        // the edge_path
        for (ArrayList<Integer> x : edge_path) {
 
            if (k == x.size())
                return 0;
 
            // Use a heap to store the array
            PriorityQueue<Integer> minHeap = new PriorityQueue<>();
 
            // 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.get(i);
                ksum += x.get(i);
 
                // Pushing edge in MinHeap
                minHeap.add(x.get(i));
 
                // If the heap size is K
                if (minHeap.size() > k) {
                    ksum -= minHeap.peek();
                    minHeap.poll();
                }
            }
 
            // If the shortestDistance is
            // smallest, 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(
            ArrayList<ArrayList<Map.Entry<Integer, Integer>>> graph,
            int n, int k, int src, int dest) {
        // Stores all the lists of edges for
        // every path traversed in DFS call
        ArrayList<ArrayList<Integer>> edge_path = new ArrayList<>();
 
        // Store the edges of the particular path
        ArrayList<Integer> temp_edge = new ArrayList<>();
 
        // Boolean visited array
        boolean[] vis = new boolean[n];
 
        // DFS Call
        dfs_all(n, src, dest, graph,
                vis, edge_path, temp_edge);
 
        return getDistance(edge_path, k);
    }
 
    // Driver Code
    public static void main(String[] args) {
        int n = 5, e = 5, k = 1;
        ArrayList<ArrayList<Map.Entry<Integer, Integer>>> graph = new ArrayList<>();
 
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
 
        // Given Adjacency List
        graph.get(0).add(new AbstractMap.SimpleEntry<>(1, 1));
        graph.get(1).add(new AbstractMap.SimpleEntry<>(0, 1));
 
        graph.get(0).add(new AbstractMap.SimpleEntry<>(4, 1));
        graph.get(4).add(new AbstractMap.SimpleEntry<>(0, 1));
 
        graph.get(1).add(new AbstractMap.SimpleEntry<>(2, 2));
        graph.get(2).add(new AbstractMap.SimpleEntry<>(1, 2));
 
        graph.get(2).add(new AbstractMap.SimpleEntry<>(3, 4));
        graph.get(3).add(new AbstractMap.SimpleEntry<>(2, 4));
 
        graph.get(4).add(new AbstractMap.SimpleEntry<>(3, 7));
        graph.get(3).add(new AbstractMap.SimpleEntry<>(4, 7));
 
        int a = 0, b = 3;
 
        System.out.println(solve(graph, n, k, a, b));
    }
}

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

C#

using System;
using System.Collections.Generic;
 
class GFG
{
    // Function to get all the possible paths from
  // source to destination
    static void DfsAll(int n, int s, int d, List<List<Tuple<int, int>>> graph, bool[] vis, List<List<int>> edgePath, List<int> tempEdge)
    {
        // One possible path
        // reached node D
        if (s == d)
        {
            edgePath.Add(new List<int>(tempEdge));
            return;
        }
        // Mark node s as visited
        vis[s] = true;
        // Calculate the number of edges with
        // node s as connection
        int edgesInA = graph[s].Count;
        // Traverse all the connections of the node s
        for (int i = 0; i < edgesInA; i++)
        {
            // If the connected node isn't visited
            if (!vis[graph[s][i].Item1])
            {
                // Push back edge value in the tempEdge
                tempEdge.Add(graph[s][i].Item2);
                // Call DFS function recursively
                DfsAll(n, graph[s][i].Item1, d, graph, vis, edgePath, tempEdge);
                // Pop back the last added edge
                tempEdge.RemoveAt(tempEdge.Count - 1);
            }
        }
        vis[s] = false;
    }
    // Function to find the minimum sum of edges from
    // source to destination
    static int GetDistance(List<List<int>> edgePath, int k)
    {
        int shortestDistance = int.MaxValue;
        // If edgePath list is empty
        // means no path exists
        if (edgePath.Count == 0)
            return -1;
        // Traverse all the vectors in the edgePath
        foreach (var x in edgePath)
        {
            if (k == x.Count)
                return 0;
            // Use heap to store the array
            SortedSet<int> minHeap = new SortedSet<int>();
            // Find the sum of all the nodes
            int sum = 0;
            int kSum = 0;
            // Find the largest K edges using minHeap
            for (int i = 0; i < x.Count; i++)
            {
                sum += x[i];
                kSum += x[i];
                // Pushing edge in MinHeap
                minHeap.Add(x[i]);
                // If heap size is K
                if (minHeap.Count > k)
                {
                    kSum -= minHeap.Min;
                    minHeap.Remove(minHeap.Min);
                }
            }
            // If the shortestDistance is smallest
            // 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
    static int Solve(List<List<Tuple<int, int>>> graph, int n, int k, int src, int dest)
    {
        // Stores all the vectors of edges for the every path traversed in DFS call
        List<List<int>> edgePath = new List<List<int>>();
        // Store the edges of particular path
        List<int> tempEdge = new List<int>();
        // Boolean visited vector
        bool[] vis = new bool[n];
        // DFS Call
        DfsAll(n, src, dest, graph, vis, edgePath, tempEdge);
        return GetDistance(edgePath, k);
    }
    // Driver Code
    static void Main()
    {
        int n = 5, k = 1;
        List<List<Tuple<int, int>>> graph = new List<List<Tuple<int, int>>>(n);
        for (int i = 0; i < n; i++)
            graph.Add(new List<Tuple<int, int>>());
        // Given Adjacency List
        graph[0].Add(new Tuple<int, int>(1, 1));
        graph[1].Add(new Tuple<int, int>(0, 1));
        graph[0].Add(new Tuple<int, int>(4, 1));
        graph[4].Add(new Tuple<int, int>(0, 1));
        graph[1].Add(new Tuple<int, int>(2, 2));
        graph[2].Add(new Tuple<int, int>(1, 2));
        graph[2].Add(new Tuple<int, int>(3, 4));
        graph[3].Add(new Tuple<int, int>(2, 4));
        graph[4].Add(new Tuple<int, int>(3, 7));
        graph[3].Add(new Tuple<int, int>(4, 7));
        int a = 0, b = 3;
        Console.WriteLine(Solve(graph, n, k, a, b));
    }
}

Javascript

function GFG(n, s, d, graph, vis, edge_path, temp_edge) {
    if (s === d) {
        edge_path.push([...temp_edge]);
        return;
    }
    vis[s] = true;
    const edges_in_a = graph[s].length;
    for (let i = 0; i < edges_in_a; i++) {
        if (!vis[graph[s][i][0]]) {
            temp_edge.push(graph[s][i][1]);
            GFG(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
function get_distance(edge_path, k) {
    let shortest_distance = Infinity;
    if (edge_path.length === 0) {
        return -1;
    }
    for (const x of edge_path) {
        if (k === x.length) {
            return 0;
        }
        // Use array to store the array
        const min_heap = [];
        let sum_val = 0;
        let k_sum = 0;
        for (let i = 0; i < x.length; i++) {
            sum_val += x[i];
            k_sum += x[i];
            min_heap.push(x[i]);
            // If array size is K
            if (min_heap.length > k) {
                const minIndex = min_heap.indexOf(Math.min(...min_heap));
                k_sum -= min_heap.splice(minIndex, 1)[0];
            }
        }
        shortest_distance = Math.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
function solve(graph, n, k, src, dest) {
    const edge_path = [];
    const temp_edge = [];
    const vis = new Array(n).fill(false);
    GFG(n, src, dest, graph, vis, edge_path, temp_edge);
    return get_distance(edge_path, k);
}
const n = 5, e = 5, k = 1;
const graph = Array.from({ length: n }, () => []);
// 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, 2]);
graph[2].push([1, 2]);
graph[2].push([3, 4]);
graph[3].push([2, 4]);
graph[4].push([3, 7]);
graph[3].push([4, 7]);
const a = 0, b = 3;
// Calling the solve function and
// printing the result
console.log(solve(graph, n, k, a, b));

Output

1

Time Complexity: O((N*log K)NN)
Auxiliary Space: O(N2)


 


Reffered: https://www.geeksforgeeks.org

Graph

Related
Count all Hamiltonian paths in a given directed graph Count all Hamiltonian paths in a given directed graph
The Earliest Moment When Everyone Become Friends The Earliest Moment When Everyone Become Friends
Count of simple cycles in an undirected graph having N vertices Count of simple cycles in an undirected graph having N vertices
Maximum element in connected component of given node for Q queries Maximum element in connected component of given node for Q queries
Implementation of Johnson’s algorithm for all-pairs shortest paths Implementation of Johnson’s algorithm for all-pairs shortest paths

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje