// CGraphAlgori.cpp: implementation of the CGraphAlgori class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "CGraphAlgori.h"
#include "math.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CGraphAlgori::CGraphAlgori()
{

}

CGraphAlgori::~CGraphAlgori()
{

}

//最小生成樹算法Prim The minimum spanning tree
int CGraphAlgori::MinSpanTree_Prim(int n, double* pdR, int* piMinTree, double& dMinTreeFee)
{
	if (n == 0 || pdR == NULL || piMinTree == NULL)
	{
		return -400;
	}

	bool* s = new bool[n];
	double* LowCost = new double[n];
	int* Closest = new int[n];


	s[1] = true;
	piMinTree[0] = 0;
	dMinTreeFee = 0;
	for (int i=1; i<n; i++)
	{
		LowCost[i] = pdR[i];
		Closest[i] = 1;
		s[i] = false;
	}

	for (i=0; i<n-1; i++)
	{
		double dMin = INF;
		int j = 1;
		for (int k=1; k<n; k++)
		{
			if ((LowCost[k]<dMin) && (!s[k]))
			{
				dMin = LowCost[k];
				j = k;
			}
		}
		s[j] = true;
		piMinTree[i+1] = j;
		dMinTreeFee += dMin;
		
		if (i != n-2)
		{
			for (k=1; k<n; k++)
			{
				if ((pdR[j*n + k]<LowCost[k]) && (!s[k]))
				{
					LowCost[k] = pdR[j*n + k];
					Closest[k] = j;
				}
			}
		}

	}


	delete[] s;
	delete[] LowCost;
	delete[] Closest;
	return 1;

}


//最短路徑Floy算法
int CGraphAlgori::MinDist_Floy(int n, double* pdR, double* pdMinDist, int* path)
{
	memcpy(pdMinDist, pdR, n*n*sizeof(double));
	memset(path, 0, n*n*sizeof(int));

	for (int i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
		{
			if (fabs(pdMinDist[i*n+j]-INF) > 0.00001)
			{
				path[i*n+j] = j;
			}
		}
	}

	for (int k=0; k<n; k++)
	{
		for (int i=0; i<n; i++)
		{
			for (int j=0; j<n; j++)
			{
				if ((pdMinDist[i*n+k] + pdMinDist[k*n+j]) < pdMinDist[i*n+j])
				{
					pdMinDist[i*n+j] = pdMinDist[i*n+k] + pdMinDist[k*n+j];
					path[i*n+j] = path[i*n+k];
				}
			}
		}
	}
	return 1;
}

//根據最短路徑Floy算法生成路徑尋找S，E節點間的路徑
int CGraphAlgori::GetPath(int S, int E, int n, int* path, PATH& PathSE)
{
	PathSE.push_back(S);
	int iNext = path[S*n+E];
	PathSE.push_back(iNext);
	while (iNext != E)
	{
		iNext = path[iNext*n+E];
		PathSE.push_back(iNext);
	}
	return 1;
}