stdafx.cpp

this is the code for finding a shortedpath in graph in althorithm

#include "stdafx.h"

// TODO: reference any additional headers you need in STDAFX.H
// and not in this file
// 0712118.cpp : Defines the entry point for the console application.
//

void dijkstra::read(char* filename)
{
	FILE* f = fopen(filename,"rt");
	if(!f)
	{
		cout<< "Can not open file";
		getch();
		exit(0);
	}
	
	fscanf(f,"%d",&this->num_of_vertices);
	for(int i=1; i<=this->num_of_vertices; i++)
	{
//		graph[i].resize(num_of_vertices);
		for(int j =1;j<=num_of_vertices; j ++)
		{
			fscanf(f,"%d", &graph[i][j]);
		}
	}
	fscanf(f,"%d", &this->source);
	fscanf(f,"%d", &this->destination);
	fclose (f);
}

void dijkstra::initialize()		//khoi tao thong so cho thuat toan
{
	for(int i=1;i<=num_of_vertices;i++)	//num_of_vertices la so dinh
	{
		mark[i]=0;				//	
		DoDai[i]=INT_MAX;	// DoDai[] la do dai cac dinh
		Nhan[i]=0;				// Nhan[] la dinh lien truoc 
	}
	DoDai[source]=0;
}

void dijkstra::algorithm()		// thuat toan chinh
{
	initialize();
	int count=0;
	int i;
	int u;
	while(mark[destination]==0)
	{
		u=minimum();		// tim dinh co do dai nho nhat trong mark
		//DoDai[++count]=u;		// thua co the bo
		if(u==-1)
		{
			break;
		}
		mark[u]=1;
		for(i=1;i<=num_of_vertices;i++)
		{
			if(graph[u][i]>0 && mark[i]!=1 && DoDai[i]>DoDai[u]+graph[u][i])
			{
				DoDai[i]=DoDai[u]+graph[u][i];
				Nhan[i]=u;
			}
		}
	}
}

int dijkstra::minimum()
{
	int min=INT_MAX;
	int i,v;
	v=-1;
	for(i=1;i<=num_of_vertices;i++)
	{
		if(mark[i]!=1)		// danh dau xem dinh i con thuoc T hay ko
		{
			if(min>=DoDai[i])
			{
				min=DoDai[i];
				v=i;
			}
		}
	}
	return v;
}

void dijkstra::printpath(int i)
{
	cout<<endl;
	if(i==source)
	{
		cout<<source;
	}
	else if(Nhan[i]==0)
		cout<<"no path from"<<source<<" to "<<i;
	else
	{
		printpath(Nhan[i]);
		cout<<".."<<i;
	}
}
void dijkstra::output()
{
	//for(int i=1;i<=num_of_vertices;i++)
	//{
	int i=destination;
		printpath(i);
		if(DoDai[i]!=999)
		cout<<"->("<<DoDai[i]<<")\n";
	//}
	cout<<endl;
}