graph.cpp

可是输出N条相同边的最短路径程序！！！！！！！1

double Graph::dijkstra( int* paths , double* dists)
{	
	int* Used = new int[_N]; 	       // label the used nodes, 0 - indicates not used.
	double* Dist = dists;

	/* Initialize */	
	unsigned i;
	for(i=0;i<_N;i++)
	{
		paths[i]= -1;	
		Used[i] = 0;
		Dist[i] = (_array[0][i] < 0.0) ? INFINITY : _array[0][i]; 
	}	
	Used[0] = 1;		               // label the start node!!!!!
	
	unsigned count = 0;	
	while(count++ < _N)
	{		
		int min_node = -1;
		double min_dist = (unsigned)INFINITY;

		/* Select */
		for(i=0;i<_N;i++)
		{
			if(Used[i] > 0)continue;   // ignore the used node
			
			if(Dist[i] < min_dist)
			{
				min_dist = Dist[i];
				min_node = i;
			}
		}
		if(min_dist == INFINITY)break;

		/* Record shortest path from the current node to start node */
		if(min_node >= 0)
		{			
			Used[min_node]  = 1;
			Dist[min_node]  = min_dist;			
		}
		if(min_node >= (int)_N-1)break;

		/* Adjust */
		for(i=0;i<_N;i++)
		{
			if( Used[i] > 0)continue;  // ignore the used node

			double w = (unsigned)_array[min_node][i];// < 0.0 ? INFINITY : _array[min_node][i];
			if( min_dist + w < Dist[i] )
			{
				Dist[i] = min_dist + w;
				paths[i] = min_node;
			}
		}       
	}

	delete[] Used;
	return (signed)Dist[_N-1];// == INFINITY ? -1 : Dist[_N-1];
}

/*
	Here, using vector is more efficient than 2-dimension dynamic array.

*/
double Graph::dijkstra( int* paths , double* dists,int start,int end)
{	
	int* Used = new int[_N]; 	       // label the used nodes, 0 - indicates not used.
	double* Dist = dists;

	/* Initialize */	
	unsigned i;
	for(i=0;i<_N;i++)
	{
		paths[i]= -1;	
		Used[i] = 0;
		Dist[i] = (_array[start][i] < 0.0) ? INFINITY : _array[start][i]; 
	}	
	Used[start] = 1;		               // label the start node!!!!!
	
	unsigned count = 0;	
	while(count++ < _N)
	{		
		int min_node = -1;
		double min_dist = (unsigned)INFINITY;

		/* Select */
		for(i=0;i<_N;i++)
		{
			if(Used[i] > 0)continue;   // ignore the used node
			
			if(Dist[i] < min_dist)
			{
				min_dist = Dist[i];
				min_node = i;
			}
		}
		if(min_dist == INFINITY)break;

		/* Record shortest path from the current node to start node */
		if(min_node >= 0)
		{			
			Used[min_node]  = 1;
			Dist[min_node]  = min_dist;			
		}
		if(min_node >= (int)end)break;///!!!!当为结束节点时推出
		/* Adjust */
		for(i=0;i<_N;i++)
		{
			if( Used[i] > 0)continue;  // ignore the used node

			double w = (unsigned)_array[min_node][i];// < 0.0 ? INFINITY : _array[min_node][i];
			if( min_dist + w < Dist[i] )
			{
				Dist[i] = min_dist + w;
				paths[i] = min_node;
			}
		}       
	}

	delete[] Used;
	return (signed)Dist[end];// == INFINITY ? -1 : Dist[_N-1];
}
unsigned Graph::addNode(unsigned ni,int preni)
{
	vector<double> newRow;
	for(int i=0;i<_size;i++)
	{
		if(i != preni)
			_array[i].push_back(_array[i][ni]);
		else
			_array[i].push_back(-1);

		newRow.push_back(-1);
	}
	newRow.push_back(-1);
	_array.push_back(newRow);

	return _size++;
}
double Graph::zuiduan( int start , int end ,  path_t& path ,double my_save[],int n,double dag[5][5])//改进的初始最短路径的值
{	
	used =new int [n];
	for(int i=0;i<n;i++)
		used[i]=0;

	double distroad=0;
double min = Dijkstra(start,end,path);                                  ;
	cout << "min dist = " << min << endl;
int num=0;
	while(path.size())
	{
        my_save[num]=path.top()+1;
		cout << path.top() +1 << " ";
		path.pop();
num++;
	}
	cout << endl;
for(int n=0;n<num;n++)//把经过的节点存入数组!!!!!!!!!!!
{int site=my_save[n];
used[site-1]++;
}

for(int i=0;i<num-1;i++)//计算最短路径的长度!
	{int sub_start= my_save[i];
	int sub_end= my_save[i+1];
		cout<<"从节点"<<sub_start<<"到节点"<<sub_end<<endl;
		distroad = distroad+dag[sub_start-1][sub_end-1];
	}
	cout<<"输出最短节点的值"<<distroad<<endl;
return distroad;}


// Find the k shortest paths
/*double tiaoshu(double k,int my_vexnum,double distroad ,Graph::path_list& paths,double **dag,int my_start)
{
	double **my_data = new double *[k];//用来初始话存储K条最短路的节点
	for(int i=0;i<my_vexnum;i++)
		my_data[i] = new double [my_vexnum];
int row=0;//用来存储行节点;
int col=0;
	for(unsigned i=0;i<paths.size();i++)	// output the k shortest paths.
	{int col=0;//用来存储列节点
	my_data[i][col]=my_start;//用来做对比的
		while(paths[i].size())
		{my_data[i][col+1]=paths[i].top()+1;
col++;
			cout << paths[i].top() + 1 << " ";
			paths[i].pop();
		
		}
		row++;
		cout << endl;
	}
	cout<<"finished"<<endl;

	for(int i=0;i<row;i++)
	{
		for(int j=0;j<my_vexnum;j++)
		{
			if(my_data[i][j]> 0)
				cout<<my_data[i][j];
			else break;

	}
	cout<<endl;
	}

	int distnum=0;
for(int i=0;i<k;i++)//计算最短路径的条数!
{//计算K次路径的长度

int sub_distroad=0;
for(int j=0;j<my_vexnum;j++)

	{
		int sub_start= my_data[i][j];
	int sub_end= my_data[i][j+1];
	if(sub_start<=0||sub_end<=0)
		break;
	else
	{cout<<"从节点"<<sub_start<<"到节点"<<sub_end<<endl;
		sub_distroad = sub_distroad+dag[sub_start-1][sub_end-1];
	}
}

if(distroad==sub_distroad)
{
	distnum++;
	for(int n=0;n<my_vexnum;n++)
		if(my_data[i][n]>0)
			cout<<my_data[i][n]<<" ";
}
else
continue;

cout<<endl;
}
return distnum;
cout<<"最短路径长度相同的路有"<<distnum<<"条"<<endl;
//改进输出
}
*/



double  Graph::kkk(double **dag,int my_start,int my_vexnum,int end,int * used)
{
	double **my_data=NULL;
	double *my_save=new double[my_vexnum];
	double **my_dag=NULL;
	int sub_distroad=0;
	double distroad=0;//用来计算最短的长度!
	int mnum=0;//用来记录有多少个最短节点数!
	int distnum=0;
for(int i=0;i<my_vexnum;i++)
		my_save[i]=0;
	Graph::path_t path;
	unsigned size = 0;
	double min =  Dijkstra(my_start,end,path);                                     ;
	//cout << "min dist = " << min << endl;
	if(min<0)
	{
		
	cout<<"从节点"<<my_start+1<<"到节点"<<end+1<<"的最短路是:"<<endl;
	cout<<"不存在最短路"<<endl;
	return 0;
	}
	else cout<<"从节点"<<my_start+1<<"到节点"<<end+1<<"的最短路是:"<<endl;

	while(path.size())
	{
        my_save[mnum]=path.top()+1;
		cout << path.top() +1 << " ";
		path.pop();
mnum++;
	}

	cout << endl;
	//测试
	/*
	for(int i=0;i<mnum;i++)
		cout<<"测试值"<<my_save[i]<<endl;
*/
cout<<"从节点"<<my_start+1<<"到节点"<<end+1;
cout<<"最短的路长为:"<<endl;
	for(int i=0;i<mnum-1;i++)//计算最短路径的长度!
	{
		int sub_start= my_save[i];
	int sub_end= my_save[i+1];
		
		//cout<<endl;
		distroad = distroad+dag[sub_start-1][sub_end-1];
	}	
	cout<<distroad<<endl;

	// Find the k shortest paths
Graph::path_list paths;
	int k = MSAforKSP(10,paths,my_start,end);
	//cout << "k = " << k << endl;	
my_data = new double *[k];//用来初始话存储K条最短路的节点
	for(int i=0;i<k;i++)
		my_data[i] = new double [my_vexnum];
	
int row=0;//用来存储行节点;
int col=0;
	for(unsigned i=0;i<paths.size();i++)	// output the k shortest paths.
	{int col=0;//用来存储列节点
	my_data[i][col]=my_start+1;//用来做对比的
		while(paths[i].size())
		{my_data[i][col+1]=paths[i].top()+1;
col++;
			//cout << paths[i].top() + 1 << " ";
			paths[i].pop();
		
		}
		row++;
		cout << endl;
	}
	//cout<<"finished"<<endl;

/*	for(int i=0;i<row;i++)
	{
		for(int j=0;j<my_vexnum;j++)
		{
			if(my_data[i][j]> 0)
				cout<<my_data[i][j];
			else break;

	}
	cout<<endl;
	}
*/
cout<<"输出相同的最短的路径"<<endl;
for(int i=0;i<k;i++)//计算最短路径的条数!
{//计算K次路径的长度
if(my_data[i][0]==my_start+1)
{
sub_distroad=0;

for(int j=0;j<my_vexnum;j++)

	{
		int sub_start= my_data[i][j];
	int sub_end= my_data[i][j+1];
	if(sub_start>0&&sub_end>0)
	{
		//cout<<"从节点"<<sub_start<<"到节点"<<sub_end<<endl;
		sub_distroad = sub_distroad+dag[sub_start-1][sub_end-1];
	}
}

if(distroad==sub_distroad)
{
	distnum++;
	int jj;
	cout<<endl;
	for(int n=0;n<mnum;n++)//输出相同的最短的路径
		if(my_data[i][n]>0.0)
		{cout<<" "<<my_data[i][n];
	jj=my_data[i][n];
	used[jj-1]++;
	}

}//改进输出
else continue;
}

}
cout<<endl;
cout<<"最短路径长度相同的路有"<<distnum<<"条"<<endl;
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
return distnum;
}