#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <math.h>

#define INT_MAX 10000
#define N 20
#define rando(max, min) \
   (((double)rand()*(max - min) / RAND_MAX) + min)

#define LB(p,P,n) (p*n/P)
#define UB(p,P,n) (LB((p+1),P,N)-1)

int main (int argc, char *argv[]) {

   int adj[N][N];
   int T[N]; // set of vertices te examined.  V is implicit.
   int d[N]; // distance vector

   // MPI bookkeeping variables
   int numP;
   int pid;
   MPI_Request sendR, recvR;
   MPI_Status sendS, recvS;
   
   // MPI Initialization
   MPI_Init(&argc, &argv);
   MPI_Comm_size(MPI_COMM_WORLD, &numP);
   MPI_Comm_rank(MPI_COMM_WORLD, &pid);

   int lower = LB(pid, numP, N);
   int upper = UB(pid, numP, N);

   // BUILD and initialize the graph we will find distances in.
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N+1; j++) {
         adj[i][j] = INT_MAX;;
      }
   }
/*
 * this was done to test.
   {
      int s = 0;
      int t = 1;
      int x = 2;
      int y = 3;
      int z = 4;

      adj[s][s] = 0;
      adj[s][t] = 10;
      adj[s][y] = 5;
      adj[t][y] = 2;
      adj[t][x] = 1;
      adj[x][z] = 4;
      adj[y][t] = 3;
      adj[y][x] = 9;
      adj[y][z] = 2;
      adj[z][s] = 7;
      adj[z][x] = 6;
   }
*/

   if (pid==0) {

      for (int redundant = 0; redundant < 2; redundant++) {
         for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
               if (rando(0.0, 1.0) < 0.5) {
                  adj[i][j] = (int) rando(1.0, 9.0); 
               }
            }
         }
      }

/*
      // PRINT the graph
      printf("the initialized graph\n"); fflush(stdout);
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
            printf("%d ", adj[i][j]);
         }
         printf("\n");
      }
*/

   }

   double t = MPI_Wtime( );
   MPI_Bcast(adj, N*N, MPI_INTEGER, 0, MPI_COMM_WORLD);

   // FIND the distances from each node s to all other nodes.
   for (int s = lower; s < upper+1; s++) { // d_s = 0 (1) // KILL change to Nbb

      // initialize d for node s
      for (int i = 0; i < N; i++) d[i] = INT_MAX; // d_i = \inf, i != s (3)
      d[s] = 0;

      for (int i=0; i < N; i++) T[i] = 1; // T = V (4)

      for (int i=0; i < N; i++) { // line 5
         // Find v_m \in T with minimum d_m (6)
         int m; 
         for (int j = 0; j < N; j++) { 
            if (T[j]) {
               m = j;
               break;
            }
         }
         for (int j=m; j < N; j++) { // find v_m \in T with minimum d_m 
            if ((d[j] < d[m]) && T[i]) {
               m = j;
            }
         }
         // End of line 6

         // for each edge (vm, vt) with vt \in T (7)
         for (int t=0; t < N; t++) {
            if (T[t]) { // vt \in T
               if ((d[t] > (d[m] + adj[m][t])) && T[t]) { // Line 8
                  d[t] = d[m] + adj[m][t];  // Line 9
               } 
            }
            T[m] = 0; // T = T - v_m (10)
         } 
      }

      t = MPI_Wtime( ) - t;

/* Uncommment to print the graph 
      for (int i=0; i < N; i++) {
         printf("s(%d) -> v(%d) = %d\n", s, i, d[i]);
      }
*/
   }

   t = MPI_Wtime( ) - t;
   printf("time of process %d is %f\n", pid, t);
}