Last Updated: 24 Jun, 2021
Min Efforts Required
Moderate
Asked in companies
The Ultimate Ninja Ankush, after training hard, goes for a good meal at the ninja cafe, for that he follows the path given on the map, which may or may not lead him to the ninja cafe. The map is a directed graph. Since he is also very lazy, he wants to minimize the effort to travel. The effort is defined as the product of all the distance it takes to reach from the dojo (source) to the ninja cafe (destination). Can you help him find the path with the minimum effort it would take The Ultimate Ninja Ankush to reach the destination?
More Formally, you are given a directed graph with ‘N’ nodes and ‘M’ edges where the distance of each edge is greater than 0, also given a source ‘src’ and a destination ‘dest’. The task is to find the minimum product of edges from src’ to ‘dest’. If there is no path from ‘src’ to ‘dest’, then return -1.
For example
Given:
‘N’ = 3, ‘M’ = 3.
‘edges’ =
[[0 1 1],
[1 2 1],
[0 2 3]]
‘src’ = 0, ‘dest’ = 2.
There are two possible paths, that is to go from node-0 to node-2 directly, which will take 2 units of effort, or go from node-0 to node-1 and then node-1 to node-2, which will take 1 unit of effort.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, ‘N,’ where ‘N’ is the number of nodes in the graph, and ‘M’ where ‘M’ is the number of edges.
The next ‘M’ line contains 3 space-separated integers ‘U’, 'V’, and ‘WT’, ‘U’ is the parent node, ‘V’ is the child node and ‘WT’ is the weight of that edge.
The last line contains 2 space-separated integers, ‘src’ and ‘dest’.
Output Format :
For each test case, You are supposed to return an integer that denotes the minimum effort required.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 100
1 <= ‘M’ <= (N*(N + 1))/2
0 <= ‘src’,’dest’ <= N
Time Limit: 1sec.
Approaches
The idea is to use the Bellman-Ford algorithm, which finds the shortest path from the source node to all the nodes in the graph.
The idea of this algorithm is to maintain a ‘distance’ array which stores the distance between the source node and all of the other nodes and do a process called ‘relaxation’ of all the edges ‘N’ - 1 time, where ‘N’ is the number of nodes.
‘Relaxation’ refers to checking for ‘U’, ‘V’, and ‘WT’ where ‘V’ is the parent node, ‘U’ is the child node and ‘WT’ is the weight of that edge and assigning ‘distance[V]’ = minimum(‘distance[V]’, ‘distance[U]’ + ‘WT’).
After ‘N-1’ relaxations, we check if there is still any possibility to optimize any distance, which implies a negative cycle.
We will use a modified Bellman-Ford for this question, i.e., instead of ‘distance[V]’ = minimum(‘distance[V]’, ‘distance[U]’ + ‘WT’), we will do ‘distance[V]’ = minimum(‘distance[V]’, ‘distance[U]’ * ‘WT’).
The steps are as follows:
- Maintain an array ‘efforts’ which stores the efforts from the ‘src’ node to the ‘dest’ node.
- Mark ‘efforts[‘src’] = 1, because the rest of the elements will be multiplied by it there will be no change.
- Loop for ‘N - 1’ times for “relaxation” of edges:
- For each edge in edges, do ‘efforts[V]’ = minimum(‘efforts[V]’, ‘efforts[U]’ * ‘WT’), where ‘V’ is the parent node, ‘U’ is the child node and ‘WT’ is the weight of that edge.
- Repeat the relaxation process once more to check if no negative cycle exists.
- If the ‘efforts[‘dest’]’ is not equal to ‘INF’, then return ‘efforts[‘dest’]’, else return -1, since there is no possible path to the ‘dest’ node.