Path with smallest product of edges with weight >= 1 | Function to return the smallest product of edges ; If the source is equal to the destination ; Initialise the priority queue ; Visited array ; While the priority - queue is not empty ; Current node ; Current product of distance ; Popping the top - most element ; If already visited continue ; Marking the node as visited ; If it is a destination node ; Traversing the current node ; If no path exists ; Driver code ; Graph as adjacency matrix ; Input edges ; print ( gr ) ; Source and destination ; Dijkstra
def dijkstra ( s , d , gr ) : NEW_LINE INDENT if ( s == d ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT pq = [ ] ; NEW_LINE pq . append ( ( 1 , s ) ) ; NEW_LINE v = [ 0 ] * ( len ( gr ) + 1 ) ; NEW_LINE while ( len ( pq ) != 0 ) : NEW_LINE INDENT curr = pq [ 0 ] [ 1 ] ; NEW_LINE dist = pq [ 0 ] [ 0 ] ; NEW_LINE pq . pop ( ) ; NEW_LINE if ( v [ curr ] ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT v [ curr ] = 1 ; NEW_LINE if ( curr == d ) : NEW_LINE INDENT return dist ; NEW_LINE DEDENT for it in gr [ curr ] : NEW_LINE INDENT if it not in pq : NEW_LINE INDENT pq . insert ( 0 , ( dist * it [ 1 ] , it [ 0 ] ) ) ; NEW_LINE DEDENT DEDENT DEDENT return - 1 ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 ; NEW_LINE gr = { } ; NEW_LINE gr [ 1 ] = [ ( 3 , 9 ) ] ; NEW_LINE gr [ 2 ] = [ ( 3 , 1 ) ] ; NEW_LINE gr [ 1 ] . append ( ( 2 , 5 ) ) ; NEW_LINE gr [ 3 ] = [ ] ; NEW_LINE s = 1 ; d = 3 ; NEW_LINE print ( dijkstra ( s , d , gr ) ) ; NEW_LINE DEDENT