// DoThi.cpp: implementation of the CDoThi class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "DoThi.h"
#include <iostream>
#include <vector>
using namespace std;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

#define VOCUC -1 
 
int nT;          
int *T;        
int *Dodai;       
int *Nhan;       

CDoThi::CDoThi()
{

}

void CDoThi::DocDoThi(char *Fname)
{
	FILE *f;
	f = fopen(Fname, "rt");

	if(!f)
	{
		cout<<"Khong mo duoc file!\n";
		exit(1);
	}

	fscanf(f, "%d", &G.n);
	fscanf(f, "%d", &this->iDinhDau);
	fscanf(f, "%d", &this->iDinhCuoi);

	G.a.resize(G.n);
	for(int i = 0; i < G.n; i++)
		G.a[i].resize(G.n);

	for(i = 0; i < G.n; i++)
	{
		for(int j = 0; j < G.n; j++)
			fscanf(f, "%d", &G.a[i][j]);
	}

	fclose(f);
}

int CDoThi::KiemTraHopLe()
{
	for(int i = 0; i < G.n; i++)
		if(G.a[i][i]!= 0)
			return 0;

	return 1;
}

int CDoThi::KiemTraVoHuong()
{
	int i, j;
	for(i = 0; i < G.n; i++)
		for(j = i + 1; j < G.n; j++)
			if(G.a[i][j] != G.a[j][i])
				return 0;

	return 1;
}

void CDoThi::Dijkstra(int iDau, int iCuoi)
{
	int v, iMin;
	nT = G.n;
	
	T =  new int[G.n];
	Dodai = new int[nT];
	Nhan = new int[nT];

	for(int i = 0; i < G.n; i++)
	{
		T[i] = 1;
		Dodai[i] = VOCUC;
		Nhan[i] = -1;
	}

	Dodai[iDau] = 0;

	while(T[iCuoi] == 1)
	{
		v = -1;
		iMin = VOCUC;
		for(i = 0; i < G.n; i++)
		{
			if(T[i] == 1)
			{
				if(SoSanhBe(Dodai[i], iMin) == 1)
				{
					iMin = Dodai[i];
					v = i;
				}

			}
		}
		
		if(v == -1)
		{
			//cout<<"Khong co duong di ngan nhat!\n";
			Nhan[iCuoi] = iDau;
			T[iCuoi] = 0;
		}

		else
		{
			T[v] = 0;

			for(int i = 0; i < G.n; i++)
			{
				if(T[i] == 1 && G.a[v][i] != 0)
				{
					if(SoSanhBe(Dodai[v] + G.a[v][i], Dodai[i]) == 1)
					{
						Dodai[i] = Dodai[v] + G.a[v][i];
						Nhan[i] = v;
					}
				}
			}
		}
	}
}

void CDoThi::KQ_Dijkstra(int iDau, int iCuoi)
{
	
//	this->Dijkstra(iDau, iCuoi);

	cout<<"Duong di ngan nhat: ";
	int i = iCuoi;
	if(Dodai[i] == -1)
		cout<<"Khong co duong di ngan nhat!\n";
	else
	{
		cout<<i;
		while(i != iDau)
		{
			i = Nhan[i];
			cout<<" <- "<<i;
		}
	}

	cout<<"\tDo dai: "<<Dodai[iCuoi]<<"\n";
}
 
void CDoThi::Tim_3_DuongDiNganNhat(FILE *f, int iDau, int iCuoi)
{
	int j;
	int i = 0;
	while(i < 3)
	{
		Dijkstra(iDau, iCuoi);

		this->KQ_Dijkstra(iDau, iCuoi);

		fprintf(f, "%d\t", Dodai[iCuoi]);

		j = iCuoi;

		while(j != iDau)
		{
			G.a[j][Nhan[j]] = 0;
			if(this->KiemTraVoHuong() == 1)
				G.a[Nhan[j]][j] = 0;

			j = Nhan[j];
		}
		
		i++;
	}
}
int CDoThi::SoSanhBe(int x, int y)
{
	if(x == VOCUC)
		return 0;
	else
		if(y == VOCUC)
			return 1;
		else
			return x < y;
}

int CDoThi::GetDinhDau()
{
	return this->iDinhDau;
}

int CDoThi::GetDinhCuoi()
{
	return this->iDinhCuoi;
}
CDoThi::~CDoThi()
{

}