/******************************************************************************
 *** FILE: floyd.cpp
 *** DATE: 10/16/2003
 *** DESC: This program illustrates the dynapic programming technique applied
 ***       to the Shortest Path problem. Floyd's algorithm is implemented to
 ***       find the prices of all shortest paths in a N-vertix graph.
 ******************************************************************************/

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;
#include <windows.h>

#define DEBUG_OUTPUT

typedef unsigned int *TPInt; // new type - pointer to an integer

const unsigned int INFINITY = 0xFFFFFFFF;

void print_distances(TPInt *W, int N)
{
	int i, j;
	cout<<"\n    ";
	for(j=0;j<N;j++)
		cout<<setw(3)<<j;
	cout<<endl;
	cout<<"    ";
	for(j=0;j<N;j++)
		cout<<"---";
	cout<<endl;
	for(i=0;i<N;i++){
		cout<<setw(3)<<i<<"|";
		for(j=0;j<N;j++)
			if( W[i][j] != INFINITY )
				cout<<setw(3)<<W[i][j];
			else
				cout<<setw(3)<<"-";
		cout<<endl;
	}
}


void floyd(TPInt *W, TPInt *D, int N)
{
	int i, j, k;
	// initializing the distance matrix
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			D[i][j] = W[i][j];

	// the algorithm itself starts here
	for(k=0;k<N;k++)
		for(i=0;i<N;i++)
			for(j=0;j<N;j++)
				if( D[i][k]!=INFINITY && D[k][j]!= INFINITY && D[i][k]+D[k][j]<D[i][j] )
					D[i][j] = D[i][k]+D[k][j];
}

void main(int argc, char *argv[])
{
	TPInt *W, *D, *V;
	int  N = (argc>1 && (N=atoi(argv[1]))) ? N : 16;

	cerr<<"Generating a random adjacent matrix for a digraph of "<<N<<" vertices ...";
	W = new TPInt[N];
	D = new TPInt[N];
	srand((unsigned)time(NULL));
	int i, j;
	for(i=0;i<N;i++){
		W[i] = new unsigned int[N];
		D[i] = new unsigned int[N];
		for(j=0;j<N;j++)
			W[i][j] = i-j ? ((rand()%3) ? rand()%N+1 : INFINITY) : 0;
	}
	cerr<<"\b\b\bdone\n";

	floyd(W, D, N);

	cout<<"Original distances:\n";
	print_distances(W, N);
	cout<<"\nThe final distances:\n";
	print_distances(D, N);
}