Karp 's minimum mean (or average) weight cycle algorithm | C # program to find minimum average weight of a cycle in connected and directed graph . ; a struct to represent edges ; vector to store edges ; 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
using System ; using System . Collections . Generic ; class GFG { static int V = 4 ; public class Edge { public int from , weight ; public Edge ( int from , int weight ) { this . from = from ; this . weight = weight ; } } static List < Edge > [ ] edges = new List < Edge > [ V ] ; static void addedge ( int u , int v , int w ) { edges [ v ] . Add ( new Edge ( u , w ) ) ; } static void shortestpath ( int [ , ] dp ) { for ( int i = 0 ; i <= V ; i ++ ) for ( int j = 0 ; j < V ; j ++ ) dp [ i , j ] = - 1 ; dp [ 0 , 0 ] = 0 ; for ( int i = 1 ; i <= V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { for ( int k = 0 ; k < edges [ j ] . Count ; k ++ ) { if ( dp [ i - 1 , edges [ j ] [ k ] . from ] != - 1 ) { int curr_wt = dp [ i - 1 , edges [ j ] [ k ] . from ] + edges [ j ] [ k ] . weight ; if ( dp [ i , j ] == - 1 ) dp [ i , j ] = curr_wt ; else dp [ i , j ] = Math . Min ( dp [ i , j ] , curr_wt ) ; } } } } } static double minAvgWeight ( ) { int [ , ] dp = new int [ V + 1 , V ] ; shortestpath ( dp ) ; double [ ] avg = new double [ V ] ; for ( int i = 0 ; i < V ; i ++ ) avg [ i ] = - 1 ; for ( int i = 0 ; i < V ; i ++ ) { if ( dp [ V , i ] != - 1 ) { for ( int j = 0 ; j < V ; j ++ ) if ( dp [ j , i ] != - 1 ) avg [ i ] = Math . Max ( avg [ i ] , ( ( double ) dp [ V , i ] - dp [ j , i ] ) / ( V - j ) ) ; } } double result = avg [ 0 ] ; for ( int i = 0 ; i < V ; i ++ ) if ( avg [ i ] != - 1 && avg [ i ] < result ) result = avg [ i ] ; return result ; } public static void Main ( String [ ] args ) { for ( int i = 0 ; i < V ; i ++ ) edges [ i ] = new List < Edge > ( ) ; addedge ( 0 , 1 , 1 ) ; addedge ( 0 , 2 , 10 ) ; addedge ( 1 , 2 , 3 ) ; addedge ( 2 , 3 , 2 ) ; addedge ( 3 , 1 , 0 ) ; addedge ( 3 , 0 , 8 ) ; Console . Write ( " { 0 : F5 } " , minAvgWeight ( ) ) ; } }