main.cpp

应用斐波纳契堆和邻接表改进单源最短路径算法

////////////////////////////////////////////////////////////////////////////////////////
#include"Graph.h"
#include<fstream.h>

///////////////////////////////////////////////////////////////////////////////////////
void main()
{
	Graph x1(5);
	int u=0,v=0,length=0,num=0;
	ifstream infile("Graph1.txt");                    //打开文件
	if(infile.fail()){
		cout<<"Error opening file Graph1.txt."<<endl; //文件不能打开返回错误
		return;
	}
	infile>>u>>v>>length;
	while(!infile.eof())
	{
		x1.Insert(u,v,length);
		infile>>u>>v>>length;
		num++;
	}
    
	srand(time(0));                                
	double start=clock();
	for(int k=0;k<100000;k++)
	{
		x1.ShortestPath(5,0);
	}
	double end=clock();
 
	cout<<"顶点数n为5,"<<"边数e为"<<setw(2)<<num<<"时间:"<<setw(6)<<(end-start)/100000<<"ms"<<endl;
	infile.close();
    
	Graph x2(7);
	num=0;
    infile.open("Graph2.txt");                    //打开文件
	if(infile.fail()){
		cout<<"Error opening file Graph2.txt."<<endl; //文件不能打开返回错误
		return;
	}
	infile>>u>>v>>length;
	while(!infile.eof())
	{
		x2.Insert(u,v,length);
		infile>>u>>v>>length;
		num++;
	}
    start=clock();
	for(k=0;k<100000;k++)
	{
		x2.ShortestPath(7,0);
	}
	end=clock();

	cout<<"顶点数n为7,"<<"边数e为"<<setw(2)<<num<<"时间:"<<setw(6)<<(end-start)/100000<<"ms"<<endl;
	infile.close();
    
	Graph x3(9);
	num=0;
    infile.open("Graph3.txt");                    //打开文件
	if(infile.fail()){
		cout<<"Error opening file Graph2.txt."<<endl; //文件不能打开返回错误
		return;
	}
	infile>>u>>v>>length;
	while(!infile.eof())
	{
		x2.Insert(u,v,length);
		infile>>u>>v>>length;
		num++;
	}
    start=clock();
	for(k=0;k<100000;k++)
	{
		x3.ShortestPath(9,0);
	}
	end=clock();
	cout<<"顶点数n为9,"<<"边数e为"<<setw(2)<<num<<"时间:"<<setw(6)<<(end-start)/100000<<"ms"<<endl;
	infile.close();
	//for(int i=0;i<7;i++)
		//cout<<x.path[i]<<",";
	cout<<endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////