Karp 's minimum mean (or average) weight cycle algorithm | a struct to represent edges ; vector to store edges @ SuppressWarnings ( " unchecked " ) ; calculates the shortest path ; initializing all distances as - 1 ; shortest distance From first vertex to in tself consisting of 0 edges ; filling up the dp table ; Returns minimum value of average weight of a cycle in graph . ; array to store the avg values ; Compute average values for all vertices using weights of shortest paths store in dp . ; Find minimum value in avg [ ] ; Driver Code
class edge : NEW_LINE INDENT def __init__ ( self , u , w ) : NEW_LINE INDENT self . From = u NEW_LINE self . weight = w NEW_LINE DEDENT DEDENT def addedge ( u , v , w ) : NEW_LINE INDENT edges [ v ] . append ( edge ( u , w ) ) NEW_LINE DEDENT V = 4 NEW_LINE edges = [ [ ] for i in range ( V ) ] NEW_LINE def shortestpath ( dp ) : NEW_LINE INDENT for i in range ( V + 1 ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT dp [ 0 ] [ 0 ] = 0 NEW_LINE for i in range ( 1 , V + 1 ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT for k in range ( len ( edges [ j ] ) ) : NEW_LINE INDENT if ( dp [ i - 1 ] [ edges [ j ] [ k ] . From ] != - 1 ) : NEW_LINE INDENT curr_wt = ( dp [ i - 1 ] [ edges [ j ] [ k ] . From ] + edges [ j ] [ k ] . weight ) NEW_LINE if ( dp [ i ] [ j ] == - 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = curr_wt NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , curr_wt ) NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT DEDENT def minAvgWeight ( ) : NEW_LINE INDENT dp = [ [ None ] * V for i in range ( V + 1 ) ] NEW_LINE shortestpath ( dp ) NEW_LINE avg = [ - 1 ] * V NEW_LINE for i in range ( V ) : NEW_LINE INDENT if ( dp [ V ] [ i ] != - 1 ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT if ( dp [ j ] [ i ] != - 1 ) : NEW_LINE INDENT avg [ i ] = max ( avg [ i ] , ( dp [ V ] [ i ] - dp [ j ] [ i ] ) / ( V - j ) ) NEW_LINE DEDENT DEDENT DEDENT DEDENT result = avg [ 0 ] NEW_LINE for i in range ( V ) : NEW_LINE INDENT if ( avg [ i ] != - 1 and avg [ i ] < result ) : NEW_LINE INDENT result = avg [ i ] NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT addedge ( 0 , 1 , 1 ) NEW_LINE addedge ( 0 , 2 , 10 ) NEW_LINE addedge ( 1 , 2 , 3 ) NEW_LINE addedge ( 2 , 3 , 2 ) NEW_LINE addedge ( 3 , 1 , 0 ) NEW_LINE addedge ( 3 , 0 , 8 ) NEW_LINE print ( minAvgWeight ( ) ) NEW_LINE