dijkstra.cpp

how to finding the best way from A to B

#include "Dijkstra.h"

void DijkstraAlg(GRAPH G,int Lenght[],int Post[],int Label[],int dinhdau,int dinhcuoi)
{
	// bien flag cho biet co duong di hay ko
	// true: la co duong di
	// false: la ko co duong di
	bool flag;
	// khoi tao cac bien so
	Init(G,dinhdau,Lenght,Post,Label);
	// khi chua tim thay dinh cuoi thi tim
	info x;
	info curX;
	Stack s;
	// khoi tao stack
	InitStack(s);
	// dua dinh dau tien vao hang doi
	x.dinh = dinhdau;
	x.lenght = Lenght[dinhdau];
	x.label = Label[dinhdau];
	x.post = Post[dinhdau];
	// lay dinh dau tien ra khoi hang doi
	Push(s,x);
	// khi con lay 1 phan tu ra duoc
	while(Pop(s,curX))
	{
		// kiem tra curX co phai la dinh ket thuc chua
		if(curX.dinh == dinhcuoi)
		{
			Lenght[curX.dinh] = curX.lenght;
			Post[curX.dinh] = curX.post;
			flag = true;
			break;
		}
		// kiem tra curX xet hay chua
		if(Label[curX.dinh] == 1)
			continue;	// xet roi thi tiep tuc lap lai 
		// them nhung dinh con cua curX vao hang doi
		for(int i=0;i<G.n;i++)
		{
			if(G.a[curX.dinh][i] != 0) // co trong so co nghia la ton tai canh noi
			{
				x.dinh = i;
				x.post = curX.dinh;
				x.label = 0;
				x.lenght = curX.lenght + G.a[curX.dinh][i];
				Push(s,x);
			}
		}
		// neu hang doi rong thi tim khong thay duong di 
		if(Empty(s))
		{
			flag = false;
			break;
		}
		// cap nhat lai cac mang 
		Lenght[curX.dinh] = curX.lenght;
		Post[curX.dinh] = curX.post;
		Label[curX.dinh] = 1;
	}
	XuatFile("output.txt",flag,dinhdau,dinhcuoi,Lenght[dinhcuoi],Post);
}
void Init(GRAPH g,int dinhdau, int Lenght[],int Post[],int Label[])
{
	for(int i=0;i<g.n;i++)
	{
		Label[i] = 0;		// danh dau chua xet
		Post[i]  = -1;		// danh dau dinh truoc la chua co
		Lenght[i] = -1;		// danh dau chieu dai la vo cung
	}
	// khoi tao chieu dai dinh dau
	Lenght[dinhdau] = 0;
}



void DocMaTranKe(char *fname, GRAPH &g,int &dinhdau,int &dinhcuoi)
{
	FILE *f = fopen(fname,"r");
	
	// kiem tra mo file thanh cong hay ko
	if(f == NULL)
	{
		printf("Khong Mo Duoc File");
		return;
	}
	// doc gia tri dinh dau va dinh cuoi 
	fscanf(f,"%d", &dinhdau);
	fscanf(f,"%d", &dinhcuoi);
	// doc gia tri cua do thi vao bien n
	fscanf(f,"%d", &g.n);

	// doc gia tri cua ma tran ke tu file
	// dung 2 vong for, dong truoc, cot sau de doc tung phan cua ma tran
	// voi a[i][j] la gia tri cua ma tran tai dong i cot j
	for(int i=0; i<g.n; i++)
	{
		for(int j=0; j<g.n; j++)
			fscanf(f,"%d", &g.a[i][j]);

	}
	
	// dong mo file
	fclose(f);

}


void XuatFile(char *fname,bool flag,int dinhdau,int dinhcuoi,int DoDai,int Post[])
{
	FILE *f = fopen(fname,"w");
	
	// kiem tra mo file thanh cong hay ko
	if(f == NULL)
	{
		printf("Khong Mo Duoc File");
		return;
	}
	if(flag == false)
		fprintf(f,"Khong Tim Duoc");
	else
	{
		fprintf(f,"%d",DoDai);
		fprintf(f,"%c",'\n');
		fprintf(f,"%d ",dinhdau);
		XuatNguoc(f,dinhcuoi,Post);
	}
	
	// dong mo file
	fclose(f);

}

// goi de qui xuat nguoc
void XuatNguoc(FILE *f,int dinhcuoi,int Post[])
{
	if(Post[dinhcuoi] == -1)
		return;
	XuatNguoc(f,Post[dinhcuoi],Post);
	fprintf(f,"%d ",dinhcuoi);

}

// ham hoan doi 2 thanh phan a->b va b->a
void HoanVi(info &a,info &b)
{
	info temp = a;
	a = b;
	b = temp;
}

// ham khoi tao stack
void InitStack(Stack &s)
{
	s.top = 0;
}

// kiem tra stack co rong hay ko
int Empty(const Stack &s)
{
	return s.top==0;
}

// them 1 phan tu vao stack vao dung vi tri
// su dung selection
int Push(Stack &s, info x)
{
	s.a[s.top] = x;
	s.top++;
	for(int i=0;i<s.top;i++)
	{
		int j=i+1;
		int max = i;
		while(j<s.top)
		{
			if(s.a[max].lenght < s.a[j].lenght)
				max = j;
			j++;
		}
		HoanVi(s.a[i],s.a[max]);
	}
	return 1;
}


// lay mot phan tu ra khoi stack
int Pop(Stack &s, info &x)
{
	if(Empty(s))
		return 0;
	x = s.a[s.top - 1];
	s.top--;
	return 1;
}