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

Apoorv
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## 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

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

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

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

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;

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

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

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

``````

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.

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