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!