Graph Theory

The problem is to find the minimum mean weighted cycle of all existing cycles in a directed Graph (V, E) if it exits. Since the graph has non-negative edges so we cannot expect the weight of the cycle fall below zero .The method used for implementation is Dynamic Programming which stores an array of all the recursive steps since the problem have both optimal substructure and overlapping sub-problems.

Assumption: The graph is non- negative weighted and is strongly connected.

Step 1: The first step involves finding the dp[i][v] which is the minimum weight used for reaching a destination v from u defined as dp [i] [v] : = min(dp [i] [v] ,dp [i-1] [u] + weight(u,v)), for i in range of N(no of vertices). This is a greedy step to traverse only those edges which encounters minimum path length.

Step 2: max (dp [n ] [v]-dp [j] [v])/n-j j in range of (N) and v is the destination of the edge set .

Step 3: min (max (dp [n] [v]-dp [j] [v])/n-j)
The min is over all the edge sets to choose the minimum weighted cycles.

Key points:

  1. The path chosen are in a progression. .
  2. A path with no cycle returns zero as the least values.
  3. The maximum value taken ensures that the path chosen is hereby the path to the original cycle .No path weight being not a part of cycles are chosen.
  4. If there is no path with progression for k edges the the value of that in the dynamic table is infinity. (Assumed)
  5. dp [i] [v]=dp [i] [u]+weight(u,v)
  6. The shortest path to any of the vertex on the minimum mean -weighted cycle can be extended along the cycle to make a shortest path to the next vertex on the cycle. Therefore max (dp [n] [v]-dp [j] [v]) /n - j for j in range of N-1. 7 .Adding a constant t the each arc or the edge the value of the mean is increased by t itself and replacing t by -min (max (dp [n] [v]-dp [j] [v]) / n - j ) we would get zero which implies that the cycle has all the paths being minimum.

Time Complexity: The algorithm runs in an O (VE) time where V is the number of vertices and E is the number of the edges.