Path with smallest product of edges with weight > 0 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; double inf = std :: numeric_limits < double > :: infinity ( ) ; double bellman ( int s , int d , vector < pair < pair < int , int > , double > > ed , int n ) { if ( s == d ) return 0 ; double dis [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) dis [ i ] = inf ; dis [ s ] = 1 ; for ( int i = 0 ; i < n - 1 ; i ++ ) for ( auto it : ed ) dis [ it . first . second ] = min ( dis [ it . first . second ] , dis [ it . first . first ] * it . second ) ; for ( auto 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 ] ; } int main ( ) { int n = 3 ; vector < pair < pair < int , int > , double > > ed ; ed = { { { 1 , 2 } , 0.5 } , { { 1 , 3 } , 1.9 } , { { 2 , 3 } , 3 } } ; int s = 1 , d = 3 ; double get = bellman ( s , d , ed , n ) ; if ( get == -2 ) cout << " Cycle ▁ Detected " ; else cout << get ; }