Path with smallest product of edges with weight > 0 | Python3 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 sys NEW_LINE inf = sys . maxsize ; NEW_LINE def bellman ( s , d , ed , n ) : NEW_LINE INDENT if ( s == d ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT dis = [ 0 ] * ( n + 1 ) ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT dis [ i ] = inf ; NEW_LINE DEDENT dis [ s ] = 1 ; NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT for it in ed : NEW_LINE INDENT dis [ it [ 1 ] ] = min ( dis [ it [ 1 ] ] , dis [ it [ 0 ] ] * ed [ it ] ) ; NEW_LINE DEDENT DEDENT for it in ed : NEW_LINE INDENT if ( dis [ it [ 1 ] ] > dis [ it [ 0 ] ] * ed [ it ] ) : NEW_LINE INDENT return - 2 ; NEW_LINE DEDENT DEDENT if ( dis [ d ] == inf ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT return dis [ d ] ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 ; NEW_LINE ed = { ( 1 , 2 ) : 0.5 , ( 1 , 3 ) : 1.9 , ( 2 , 3 ) : 3 } ; NEW_LINE s = 1 ; d = 3 ; NEW_LINE get = bellman ( s , d , ed , n ) ; NEW_LINE if ( get == - 2 ) : NEW_LINE INDENT print ( " Cycle ▁ Detected " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( get ) ; NEW_LINE DEDENT DEDENT