mean-weight-cycle-of-a-graph.cpp

/**
 * @file mean-weight-cycle-of-a-graph.cpp
 * @author prakash (prakashsellathurai@gmail.com)
 * @brief
 You are given a weighted directed graph G with n vertices and m edges. The
mean weight of a cycle is the sum of its edge weights divided by the number of
its edges. Find a cycle in G of minimum mean weight.
 * @version 0.1
 * @date 2021-08-08
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int V = 4;

// a struct to represent edges
struct edge {
  int from, weight;
};

// vector to store edges
vector<edge> edges[V];

void addedge(int u, int v, int w) { edges[v].push_back({u, w}); }

// calculates the shortest path
void shortestpath(int dp[][V]) {
  // initializing all distances as -1
  for (int i = 0; i <= V; i++)
    for (int j = 0; j < V; j++)
      dp[i][j] = -1;

  // shortest distance from first vertex
  // to in tself consisting of 0 edges
  dp[0][0] = 0;

  // filling up the dp table
  for (int i = 1; i <= V; i++) {
    for (int j = 0; j < V; j++) {
      for (int k = 0; k < edges[j].size(); 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] = min(dp[i][j], curr_wt);
        }
      }
    }
  }
}

// Returns minimum value of average weight of a
// cycle in graph.
double minAvgWeight() {
  int dp[V + 1][V];
  shortestpath(dp);

  // array to store the avg values
  double avg[V];
  for (int i = 0; i < V; i++)
    avg[i] = -1;

  // Compute average values for all vertices using
  // weights of shortest paths store in dp.
  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] = max(avg[i], ((double)dp[V][i] - dp[j][i]) / (V - j));
    }
  }

  // Find minimum value in avg[]
  double result = avg[0];
  for (int i = 0; i < V; i++)
    if (avg[i] != -1 && avg[i] < result)
      result = avg[i];

  return result;
}

int main() {
  addedge(0, 1, 1);
  addedge(0, 2, 10);
  addedge(1, 2, 3);
  addedge(2, 3, 2);
  addedge(3, 1, 0);
  addedge(3, 0, 8);

  cout << minAvgWeight();

  return 0;
}