Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach
3.1.
Algorithm
3.2.
C++ implementation
3.3.
Java implementation
3.4.
Python implementation
3.5.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a graph?
4.2.
What is a weighted graph?
4.3.
What is a directed graph?
4.4.
How to find the shortest path in the weighted graph?
4.5.
What is the algorithm used to find the minimum cost path in a directed graph via a given set of necessary nodes?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Minimum Cost Path in a Directed Graph via a Given Set of Necessary Nodes

Author Apoorv
2 upvotes

Introduction

Graphs are one of the topics in Data Structures where most people tend to struggle a bit. However, once you understand the basic concepts thoroughly, it is all a piece of cake. You must have encountered the Minimum cost path problem in your day-to-day life as well say when you have to travel from one place to another, and there are multiple ways to go there. If you had to reach there in the least possible time and through a certain place in between, you would compute the route accordingly in your head to your destination or take the help of any GPS services that automatically guide you through the most optimal path. In this problem, we are going to discuss how to calculate the optimal path from one node to another.

Problem statement

We are given a directed graph 'graph' and an array 'mustpassnodes[]' containing some set of graph nodes. We are also given with source vertex 'source' and destination vertex 'dest,' the task is to visit all the nodes of the array 'mustpassnodes[]' and find the minimum cost path from the source vertex to the destination vertex, i.e., minimum cost path in a directed graph.

Example

Let the array be mustpassnodes  = {1} , source vertex be , source =  0 , destination vertex be ,dest = 3 and the graph is given below

weighted Directed Graph

Output 

8

Explanation:

Here from source vertex 0 to destination vertex 3 there are a lot of paths but we have to  choose the path that includes the nodes of array 'mustpassnodes' so considering this fact,there are two paths from 0 to 3 including the mustpassnodes 

Path 1 : 0- - - 1 - - - 3 = {5 + 3 } = {8} 

Path 2: 0 - - - 2 - - - 1 - - - 3 = {3 + 2 + 3} = {8}

Both these path 1 and path 2 give the same cost here we have to print the minimum cost path in a directed graph that is minimumcostpathinadirectedgraph(path1, path2) = min(8, 8) = 8

Recommended to try the problem by yourself before moving on to the solution

Approach

To find the minimum cost path in a directed graph, the approach is to employ Depth-First-Search traversal to address the problem. DFS is commonly used to determine the shortest paths in a graph, and the DFS can calculate the minimum distance of all nodes from the source, intermediate nodes, and destination nodes.

Algorithm

  • Set the value of ‘minSum’ to INT MAX.
  • Using DFS, traverse the graph starting at node Source.
  • Mark each of the source's neighboring nodes as a new source and conduct DFS from that node.
  • Once you've reached destination node D, see if all of the intermediate nodes have been visited.
  • If all the intermediated nodes have been visited, update the value of ‘minSum’ form ‘minSum’ and ‘currsum’ and return ‘minSum’
  • Return ‘minSum’ simply if all intermediate nodes have not been visited.
  • After DFS call, make the source vertex as unvisited
  • Obtain the final value of minSum and print it.

C++ implementation

#include <bits/stdc++.h>
using namespace std;

// Stores minimum-cost of path from source
int minSum = INT_MAX;

// Declaring directed graph
unordered_map<int,vector<pair<int,int> > > graph;

// Function to perform dfs from source vertex to find minimum cost path in a directed graph
void minPathSum(vector<int>& vis,vector<int> mustpassnodes,int src, int dest, int currSum)
{

    // If destination is reached
    if (src == dest) {

        // Set one flag variable here to true
        bool check = true;

        // Visit all the intermediate nodes to find minimum cost path in a directed graph
        for (int i : mustpassnodes) {
            
            // If any must pass node is not visited than make check false
            if (!vis[i]) {
                check = false;
                break;
            }
        }

        // If all the must pass nodes have been visited
        if (check)

            // Update the minSum
            minSum = min(minSum, currSum);

        return;
    }
    else {

        // Mark the current node as visited
        vis[src] = 1;

        // Traverse all the adjacent nodes of current node
        for (auto node : graph[src]) {

            if (!vis[node.first]) {

                // Mark the neighbour visited
                vis[node.first] = 1;

                // Applying dfs on current source vertex
                minPathSum(vis,mustpassnodes, node.first,dest, currSum + node.second);

                // Mark the neighbour unvisited
                vis[node.first] = 0;
            }
        }

        // Mark the source unvisited
        vis[src] = 0;
    }
}

int main()
{

    // Stores the directed graph
    graph[0] = { { 1, 5 }, { 2, 3 } };
    graph[1] = { { 3,3} };
    graph[2] = { { 1, 2 },{3,5},{4,6} };
    graph[3] = {  };
    graph[4] = { {3,1} };

    // Total number of nodes in directed graph
    int totalNodes = 5;

    // Source node
    int source = 0;

    // Destination node
    int dest = 3;

    // Maintain a track of all visited and unvisited nodes
    vector<int> vis(totalNodes, 0);

    // Stores intermediate nodes that need to be include in source destination path
    vector<int> mustpassnodes{ 1 };

    // dfs call to find minimum cost path in a directed graph
    minPathSum(vis,mustpassnodes,source, dest, 0);

    // Print the min cost path sum from intermediate nodes
    minSum == INT_MAX?cout << "NO PATH":cout << minSum ;
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

8

Java implementation

import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
   static int minSum = Integer.MAX_VALUE;
   // Function to perform dfs from source vertex to find minimum cost path in a directed graph
   static void getMinPathSum(Map<Integer, ArrayList<pair>> graph, boolean[] vis, ArrayList<Integer> mustpassnodes, int src, int dest, int currSum) {
       // If destination is reached
       if (src == dest) {
           // Set flag to true
           boolean check = true;
   
           // Visit all the intermediate nodes
           for(int i : mustpassnodes) {
               
               // If any intermediate node
               // is not visited
               if (!vis[i]) {
                   check = false;
                   break;
               }
           }
   
           // If all intermediate
           // nodes are visited
           if (check) {
               // Update the minSum
               minSum = Math.min(minSum, currSum);
           }
           return;
       } else {
           
           // Mark the current node
           // visited
           vis[src] = true;
   
           // Traverse adjacent nodes
           for(pair node : graph.get(src)) {
               if (!vis[node.first]) {
                   // Mark the neighbour visited
                   vis[node.first] = true;
   
                   // Find minimum cost path
                   // considering the neighbour
                   // as the source
                   getMinPathSum(graph, vis, mustpassnodes, node.first, dest, currSum + node.second);
   
                   // Mark the neighbour unvisited
                   vis[node.first] = false;
               }
           }
           vis[src] = false;
       }
   }
   
   // Driver code
   public static void main(String[] args) {
       
       // Stores the graph
       Map<Integer, ArrayList<pair>> graph = new HashMap<>();
   
       for(int i = 0; i <= 6; i++) {
           graph.put(i, new ArrayList<pair>());
       }
   
       graph.get(0).add(new pair(1, 5));
       graph.get(0).add(new pair(2, 3));
       graph.get(1).add(new pair(3, 3));
       graph.get(2).add(new pair(1, 2));
       graph.get(2).add(new pair(3, 5));
       graph.get(2).add(new pair(4, 6));
       graph.get(4).add(new pair(3, 1));
   
       // Number of nodes
       int n = 5;
   
       // Source
       int source = 0;
   
       // Destination
       int dest = 3;
   
       // Keeps a check on visited
       // and unvisited nodes
       boolean[] vis = new boolean[n];
       ArrayList<Integer> mustpassnodes = new ArrayList<>(Arrays.asList(1));
   
       getMinPathSum(graph, vis, mustpassnodes, source, dest, 0);
   
       // If no path is found
       if (minSum == Integer.MAX_VALUE) {
           System.out.println(-1);
       } else {
           System.out.println(minSum);
       }
   }
  
   static class pair {
       int first, second;
       public pair(int f, int s) {
           this.first = f;
           this.second = s;
       }
   }
}
You can also try this code with Online Java Compiler
Run Code

 

Output:

8

Python implementation

# Stores minimum-cost of path from source
minSum = 1000000000
 # Function to Perform BFS on graph g starting from vertex v
def getMinPathSum(graph, vis, necessary, src, dest, currSum):
   
   global minSum
   
   # If destination is reached
   if (src == dest):
       # Set flag to true
       flag = True;
        # Visit all the intermediate nodes
       for i in necessary:
           # If any intermediate node
           # is not visited
           if (not vis[i]):
               flag = False;
               break;
   
       # If all intermediate
       # nodes are visited
       if (flag):
           # Update the minSum
           minSum = min(minSum, currSum);
       return;
   
   else:
       # Mark the current node visited
       vis[src] = True;
       # Traverse adjacent nodes
       for node in graph[src]:
           if not vis[node[0]]:
               # Mark the neighbour visited
               vis[node[0]] = True;
               # Find minimum cost path
               # considering the neighbour
               # as the source
               getMinPathSum(graph, vis, necessary, node[0], dest, currSum + node[1]);
               # Mark the neighbour unvisited
               vis[node[0]] = False;
              
       # Mark the source unvisited
       vis[src] = False;
# Driver Code
if __name__=='__main__':
   
   # Stores the graph
   graph=dict()
  
   graph[0] = [ [ 1, 5 ], [ 2, 3 ] ];
   graph[1] = [ [ 3, 3] ];
   graph[2] = [ [ 1, 2 ], [ 3, 5 ], [ 4, 6 ] ];
   graph[3] = [  ];
   graph[4] = [ [ 3,1 ] ];
   
   # Number of nodes
   n = 5;
    # Source
   source = 0;
    # Destination
   dest = 3;
    vis=[ False for i in range(n + 1)]
    # Stores intermediate nodes
   necessary = [ 1 ];
    getMinPathSum(graph, vis, necessary, source, dest, 0);
    # If no path is found
   if (minSum == 1000000000):
       print(-1)
   else:
       print(minSum)

You can also try this code with Online Python Compiler
Run Code

 

Output:

8

Complexity Analysis

Time Complexity: O(N + M)

The time complexity to find the minimum cost path in a directed graph is O(N + M), where N is the number of nodes in the graph and M is the number of edges in the graph. In DFS, each node is traversed exactly once. As a result, DFS has a time complexity of at least O(N). Now, any additional complexity comes from how you discover all the outgoing paths or edges for each node, which depends on how your directed graph is implemented. If the directed graph is implemented using an adjacency matrix, then the time complexity would be O(N*N) and, in the case of the adjacency list O(N + M).

Space Complexity: O(N)

The space complexity to find the minimum cost path in a directed graph is O(N), where N is the number of nodes in the graph since we create a visited array of size N, which takes extra space in the implementation.

Frequently Asked Questions

What is a graph?

The link between lines and points is described by a graph, which is a mathematical description of a network.

What is a weighted graph?

A weighted graph is one in which each branch has a numerical weight. As a result, a weighted graph is a sort of labeled graph in which the labels are numbers (which are usually taken to be positive).

What is a directed graph?

A directed graph consists of a set of connected objects (called vertices or nodes) with all connections pointing from one vertex to the next. A directed graph is also known as a directed network or a digraph. On the other hand, an undirected graph is one in which the edges are bidirectional.

How to find the shortest path in the weighted graph?

The two most famous algorithms for finding the shortest distance in the weighted graph use 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).

What is the algorithm used to find the minimum cost path in a directed graph via a given set of necessary nodes?

The algorithm used to find the minimum cost path in a directed graph via a given set of necessary nodes is depth-first search (DFS) from the source node to the destination node and then checking if all the necessary nodes are visited.

Conclusion

This article discussed finding a Minimum Cost Path in a directed graph via a given set of intermediate nodes. Along with the answer, we also discussed the time and space complexity.

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

Refer to our guided paths on Coding Ninjas Studio to learn more about Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; take a look at the interview experiences and interview bundle for placement preparations.

Recommended Readings:


Also, check out these. 

Do upvote our blog to help other ninjas grow.

Happy Learning!

Live masterclass