using namespace std;
#include <iostream>

/* 
  Finding the path matrix (or transitive closure) of a graph using a
  matrix representation and Warshall's algorithm.

  This algorithm will also compute the "next-hop" matrix, with which
  one can determine the exact path to traverse between any pair of nodes.
  
  We will use dynamically allocated, 2d arrays of size nXn.  If static
  arrays were used, we won't be able to write the "transclosure" function
  below without knowing the sizes of the matrices beforehand.
*/

/*
 -1 is used to represent infinity.  An alternative is 0x7fffffff, but 
becarefull with overflow.
*/
 

int addcost(int a, int b)
{
  if (a > 0 && b> 0) return a+b; else return -1;
}


void transclosure(int **M, int **N, int n)
{
  int i, j, k;
  for(k=0;k<n;k++)
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
	{
	  int s = addcost(M[i][k],M[k][j]);
	  if (s>0 && (s<M[i][j] || M[i][j]<0))  // CAREFUL!
	    { 
	      M[i][j] = s;
  	      N[i][j] = N[i][k];
	    }
	} // for j
}

void printdy(int **A, int r, int c)  // for printing array
{
  int i, j;
  for(i=0;i<r;i++) 
    { for (j=0;j<c;j++) cout << A[i][j] << "  ";
      cout << "\n";
    }
}


// test:
int main()
{
  // testing program with 4x4 matrix:
  int n = 4;
  int** M = new int*[n];  // cost/adjacency matrix
  int** N = new int*[n];  // next-hop matrix:
                          // N[i][j] is the next step to take to get from
                          // node i to node j.
  for(int i=0;i<n;i++) M[i] = new int[n];
  for(int i=0;i<n;i++) N[i] = new int[n];
  for(int i=0;i<n;i++) for(int j=0;j<n;j++) M[i][j] = -1;
  // set edges and costs:
  M[0][1] = 2;  M[0][3] = 9;
  M[1][2] = 3;
  M[2][3] = 2;
  M[3][1] = 1;
  // set initial next-hop matrix:
  for(int i=0;i<n;i++)
     for(int j=0;j<n;j++) 
       { if (M[i][j]>0) N[i][j] = j; else N[i][j] = i; }


  cout << "adjacency matrix:\n";
  printdy(M,n,n);
  transclosure(M,N,n);
  cout << "final path cost matrix: \n";
  printdy(M,n,n);
  cout << "final next hop matrix: \n";
  printdy(N,n,n);
  return 0;
}

/* Excercise: write a procedure 

   void printpath(int ** N, int n, int i, int j)
 
   which, given the final next-hop matrix, it's size (nXn) and
   start and destination vertices (i and j), should print the nodes
   that should be visited on the shortest path from i to j, or "no path"
   if none exists
*/


/*
   Warshall's algorithm can thus be adopted to find the minimum-cost
   path between vertices.  However, its complexity measure relative
   to the number of vertices is clearly O(n^3), which is costly. 
*/