shortest path algorithm and file saving

**Micko** · 05-07-2004

Hi,
finally I manage to implement all pairs shortest path algorithm (Flloyd I think)
this is doing a good job.
Here's the code:

Code:

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

class Graph
{
	int** adjmatrix;
	int** costmatrix;
	int** path_matrix;
	int *niz;
	int size;
	void init_adjmatrix();
	void init_costmatrix();
	void load_adjmatrix();
	void load_costmatrix(int,int);
	void init_path_matrix();
	void show_matrix_shortest_paths();
	
public:
	Graph(int);
	~Graph();
	void setup_matrices();
	void show_path(int,int);
	int find_shortest_path_cost(int,int);
	void show_adjmatrix()
	{
		for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<adjmatrix[i][j];
	}
	
};

Graph::Graph(int siz):size(siz)
{
	niz=new int[size];
	adjmatrix=new int* [size];
	costmatrix=new int* [size];
	path_matrix=new int*[size];
	for(int i=0;i<size;i++)
	{
		adjmatrix[i]=new int[size];
		costmatrix[i]=new int[size];
		path_matrix[i]=new int[size];
		niz[i]=0;
	}	
	setup_matrices();
	
}
Graph::~Graph()
{
	for(int i=0;i<size;i++)
	{
		delete adjmatrix[i];
		delete costmatrix[i];
		delete path_matrix[i];
	}
	delete adjmatrix;
	delete costmatrix;
	delete path_matrix;
}
void Graph::setup_matrices()
{
	init_path_matrix();
	init_adjmatrix();
	load_adjmatrix();
	init_costmatrix();
	
}
void Graph::init_adjmatrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			adjmatrix[i][j]=0;
}
void Graph::init_costmatrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			costmatrix[i][j]=adjmatrix[i][j];
}
void Graph::load_adjmatrix()
{
	int i,j,cost;;
	char answer;
	
		const int infinite=999999;
		for(i=0;i<size;i++)
		{
			for(j=0;j<size;j++)
			{
			
			
				if((i!=j)&& (adjmatrix[i][j]==0)){
				//adjmatrix entered by user
				cout<<"Is there connection between "<<i<<" i node "<<j<<" ?"<<endl;
				cout<<"Your answer (y for yes,any key for no): ";
				cin>>answer;
				if((answer=='y')||(answer=='Y'))
				{
					cout<<"Enter cost: ";
					cin>>cost;
					adjmatrix[i][j]=adjmatrix[j][i]=cost;
					path_matrix[i][j]=j;path_matrix[j][i]=i;
				}
				else
					adjmatrix[i][j]=adjmatrix[j][i]=path_matrix[i][j]=path_matrix[j][i]=infinite;
			}
				
		}
		
	}

}

void Graph::load_costmatrix(int beg,int end)
{
	
	const int infinite=999999;
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<size;j++)
		{
			for(int k=0;k<size;k++)
			{
				if(costmatrix[i][k]>0)
				{
					if((!costmatrix[j][k])||
						(costmatrix[i][k]+costmatrix[j][i]
						<costmatrix[j][k]))
					{
						costmatrix[j][k]=costmatrix[i][k]+costmatrix[j][i];
						path_matrix[j][k]=path_matrix[j][i];
					}
				}
			}
		}
	}
}
int Graph::find_shortest_path_cost(int i,int j)
{
	load_costmatrix(i,j);
	return costmatrix[i][j];
}
void Graph::init_path_matrix()
{
	const int infinite=999999;
	for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
		{
			if(i==j)
				path_matrix[i][j]=i;
			else
				path_matrix[i][j]=infinite;
		}
}
void Graph::show_path(int start,int end)
{
	int k=-1;
	cout<<"Path is: "<<start;
	while(k!=end)
	{
		k=path_matrix[start][end];
		cout<<" "<<k;
		start=k;
	}
}
void Graph::show_matrix_shortest_paths()
{
for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<path_matrix[i][j];
}
int main()
{
	int node_number,source,destination,cost;

	cout<<"Enter number of nodes: ";
	cin>>node_number;
	Graph graph_obj(node_number);

	cout<<"Enter source index: ";
	cin>>source;
	if(source>node_number-1)
	{
		cout<<"Error!"<<endl;
		return -1;
	}
	cout<<"Enter destination index: ";
	cin>>destination; 
	if(destination>node_number-1)
	{
		cout<<"Error"<<endl;
		return -1;
	}
	cost =graph_obj.find_shortest_path_cost(source,destination);

	cout<<"The shortest path between "<<source<<" i node "<<destination<<
		" has cost "<<cost<<"!"<<endl;
	
	graph_obj.show_path(source,destination);
	
	return 0;
}

This implementation have some weaknees:
First this variable infinite is define as 999999 this is pretty much unfortunate.
Do you have any suggestion regarding this issue?
Second, there are weak chacking of user inputs, but I think I can manage this.
Third, every time program is started user must enter graph manualy. Idea was to make this using files. So one can eneter name of file where graph is stored. First data in file would be int that represent number of nodes vertices, and then adjmatrix elements.
I not good at working with files so I manage to screw this up with the following code:

Code:

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

class Graph
{
	int** adjmatrix;
	int** costmatrix;
	int** path_matrix;
	int *niz;
	int size;
	void init_adjmatrix();
	void init_costmatrix();
	void load_adjmatrix();
	void load_costmatrix(int,int);
	void init_path_matrix();
	void show_matrix_shortest_paths();
	FILE *fp;
	
public:
	Graph(int,FILE*);
	~Graph();
	void setup_matrices(FILE *);
	void show_path(int,int);
	int find_shortest_path_cost(int,int);
	void show_adjmatrix()
	{
		for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<adjmatrix[i][j];
	}
	
};

Graph::Graph(int siz,FILE* f):size(siz),fp(f)
{
	niz=new int[size];
	adjmatrix=new int* [size];
	costmatrix=new int* [size];
	path_matrix=new int*[size];
	for(int i=0;i<size;i++)
	{
		adjmatrix[i]=new int[size];
		costmatrix[i]=new int[size];
		path_matrix[i]=new int[size];
		niz[i]=0;
	}	
	setup_matrices(fp);
	
}
Graph::~Graph()
{
	for(int i=0;i<size;i++)
	{
		delete adjmatrix[i];
		delete costmatrix[i];
		delete path_matrix[i];
	}
	delete adjmatrix;
	delete costmatrix;
	delete path_matrix;
}
void Graph::setup_matrices(FILE *f)
{
	fp=f;
	init_path_matrix();
	init_adjmatrix();
	load_adjmatrix();
	init_costmatrix();
	
}
void Graph::init_adjmatrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			adjmatrix[i][j]=0;
}
void Graph::init_costmatrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			costmatrix[i][j]=adjmatrix[i][j];
}
void Graph::load_adjmatrix()
{
	int i,j,cost;;
	char answer;
	char s[80];
	if(fp!=NULL)
	{
		for(int i=0;i<size;i++)
			for(j=0;j<size;j++)
				fread(&adjmatrix[i][j],sizeof(int),1,fp);
	}
	else
	{
		cout<<"File doesn't exist! Creating new..."<<endl;
		cout<<"Enter new name: ";
		cin>>s;
		fp=fopen(s,"wb");
		if(fp==NULL)
		{
			cout<<"Error!";
			exit(1);
		}
		const int infinite=999999;
		fwrite(&size,sizeof(int),1,fp);
		for(i=0;i<size;i++)
		{
			for(j=0;j<size;j++)
			{
			
			
				if((i!=j)&& (adjmatrix[i][j]==0)){
				//adjmatrix entered by user
				cout<<"Is there connection between "<<i<<" i node "<<j<<" ?"<<endl;
				cout<<"Your answer (y for yes,any key for no): ";
				cin>>answer;
				if((answer=='y')||(answer=='Y'))
				{
					cout<<"Enter cost: ";
					cin>>cost;
					adjmatrix[i][j]=adjmatrix[j][i]=cost;
					path_matrix[i][j]=j;path_matrix[j][i]=i;
				}
				else
					adjmatrix[i][j]=adjmatrix[j][i]=path_matrix[i][j]=path_matrix[j][i]=infinite;
			}
				fwrite(&adjmatrix[i][j],sizeof(int),1,fp);
		}
			fclose(fp);
	}

}
}
void Graph::load_costmatrix(int beg,int end)
{
	
	const int infinite=999999;
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<size;j++)
		{
			for(int k=0;k<size;k++)
			{
				if(costmatrix[i][k]>0)
				{
					if((!costmatrix[j][k])||
						(costmatrix[i][k]+costmatrix[j][i]
						<costmatrix[j][k]))
					{
						costmatrix[j][k]=costmatrix[i][k]+costmatrix[j][i];
						path_matrix[j][k]=path_matrix[j][i];
					}
				}
			}
		}
	}
}
int Graph::find_shortest_path_cost(int i,int j)
{
	load_costmatrix(i,j);
	return costmatrix[i][j];
}
void Graph::init_path_matrix()
{
	const int infinite=999999;
	for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
		{
			if(i==j)
				path_matrix[i][j]=i;
			else
				path_matrix[i][j]=infinite;
		}
}
void Graph::show_path(int start,int end)
{
	int k=-1;
	cout<<"Path is: "<<start;
	while(k!=end)
	{
		k=path_matrix[start][end];
		cout<<" "<<k;
		start=k;
	}
}
void Graph::show_matrix_shortest_paths()
{
for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<path_matrix[i][j];
}
int main()
{
	int node_number,source,destination,cost;

	cout<<"Enter file name  contains graph infos: ";
	cout.flush();
	char s[BUFSIZ];;
	cin.getline(s,BUFSIZ-1,'\n');
	FILE *fp=fopen(s,"rb");

	if(fp==NULL){
		cout<<"Enter number of nodes: ";
	
		cin>>node_number;Graph graph_obj(node_number,fp);
	}

	fread(&node_number,sizeof(int),1,fp);
	
	Graph graph_obj(node_number,NULL );

	

	cout<<"Enter source index: ";
	cin>>source;
	if(source>node_number-1)
	{
		cout<<"Error!"<<endl;
		return -1;
	}
	cout<<"Enter destination index: ";
	cin>>destination; 
	if(destination>node_number-1)
	{
		cout<<"Error"<<endl;
		return -1;
	}
	cost =graph_obj.find_shortest_path_cost(source,destination);

	cout<<"The shortest path between "<<source<<" i cvora "<<destination<<
		" has cost "<<cost<<"!"<<endl;
	
	graph_obj.show_path(source,destination);
	
	return 0;
}

This has one weakness: it's not working.
I'm pretty tired of this, so I must ask for your help. I'm sure there is more elegant and simpler way
of soving this.
I tried myself and didn't make it.
I hope you will help me

Thank you very much!!!

Thread: shortest path algorithm and file saving

Thread Tools

Search Thread

Display

shortest path algorithm and file saving

Similar Threads

algorithm for duplicate file checking help

opening empty file causes access violation

search algorithm

disk file search algorithm

Simple File Creation Algorithm