Path with smallest product of edges with weight>0

Given a directed graph with N nodes and E edges where the weight of each edge is > 0, also given a source S and a destination D. The task is to find the path with the minimum product of edges from S to D. If there is no path from S to D, then print -1.

Examples:

Input: N = 3, E = 3, Edges = {{{1, 2}, 0.5}, {{1, 3}, 1.9}, {{2, 3}, 3}}, S = 1, and D = 3 
Output: 1.5 
Explanation: 
The shortest path will be 1->2->3 
with value 0.5*3 = 1.5

Input: N = 3, E = 3, Edges = {{{1, 2}, 0.5}, {{2, 3}, 0.5}, {{3, 1}, 0.5}}, S = 1, and D = 3 
Output: cycle detected 

Approach: The idea is to use the bellman ford algorithm. It is because Dijkstra’s algorithm cannot be used here as it works only with non-negative edges. It is because while multiplying values between [0-1), the product keeps decreasing indefinitely and 0 is returned finally.
Moreover, cycles need to be detected because if a cycle exists, the product of this cycle will indefinitely decrease the product to 0 and the product will tend to 0. For, simplicity, we will report such cycles. 
The following steps can be followed to compute the result: 

1. Initialize an array, dis[] with initial value as ‘inf’ except dis[S] as 1.
2. Run a loop from 1 – N-1. For each edge in the graph:
   • dis[edge.second] = min(dis[edge.second], dis[edge.first]*weight(edge))
3. Run another loop for each edge in the graph, if any edge exits with (dis[edge.second] > dis[edge.first]*weight(edge)), then cycle is detected.
4. If dist[d] in infinity, return -1, else return dist[d].

Below is the implementation of the above approach:  

1.5

Time complexity: O(E*V)
 Auxiliary Space: O(V).