Path with smallest product of edges with weight > 0 | Java implementation of the approach ; Function to return the smallest product of edges ; If the source is equal to the destination ; Array to store distances ; Initialising the array ; Bellman ford algorithm ; Loop to detect cycle ; Returning final answer ; Driver code ; Input edges ; Source and Destination ; Bellman ford
import java . util . ArrayList ; import java . util . Arrays ; import java . util . PriorityQueue ; class Pair < K , V > { K first ; V second ; public Pair ( K first , V second ) { this . first = first ; this . second = second ; } } class GFG { static final float inf = Float . POSITIVE_INFINITY ; static float bellman ( int s , int d , ArrayList < Pair < Pair < Integer , Integer > , Float > > ed , int n ) { if ( s == d ) return 0 ; float [ ] dis = new float [ n + 1 ] ; Arrays . fill ( dis , inf ) ; dis [ s ] = 1 ; for ( int i = 0 ; i < n - 1 ; i ++ ) for ( Pair < Pair < Integer , Integer > , Float > it : ed ) dis [ it . first . second ] = Math . min ( dis [ it . first . second ] , dis [ it . first . first ] * it . second ) ; for ( Pair < Pair < Integer , Integer > , Float > it : ed ) { if ( dis [ it . first . second ] > dis [ it . first . first ] * it . second ) return - 2 ; } if ( dis [ d ] == inf ) return - 1 ; else return dis [ d ] ; } public static void main ( String [ ] args ) { int n = 3 ; ArrayList < Pair < Pair < Integer , Integer > , Float > > ed = new ArrayList < > ( Arrays . asList ( new Pair < Pair < Integer , Integer > , Float > ( new Pair < Integer , Integer > ( 1 , 2 ) , 0.5f ) , new Pair < Pair < Integer , Integer > , Float > ( new Pair < Integer , Integer > ( 1 , 3 ) , 1.9f ) , new Pair < Pair < Integer , Integer > , Float > ( new Pair < Integer , Integer > ( 2 , 3 ) , 3f ) ) ) ; int s = 1 , d = 3 ; float get = bellman ( s , d , ed , n ) ; if ( get == - 2 ) System . out . println ( " Cycle ▁ Detected " ) ; else System . out . println ( get ) ; } }