test.cpp

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

/*
	Graph library Demo.
	David D.	2006
*/

#include "Graph.h"


using namespace std;
using namespace Mido::Utility;

const int N = 5;
 double dag[N][N] = { 	{-1, 1,1,1,-1},
							{-1,-1, 1,-1,1},
							{-1,-1,-1, 1,1},
							{-1,-1,-1,-1,1},
							{-1,-1, -1,-1,-1}};
 double sub_dag;

int main(int argc, char** argv)
{	
	//自己的初始化,可以定义成为函数
char t;
	int my_vexnum;
	double **my_dag=NULL;
	//用来存储最短的节点！
double my_check[N]={0};//用来存储对比的最短的节点！

int my_start;
	int my_end;
	cout<<endl;
	cout<<"copyright Grahp 1.0 anthor kongliang email:[e-mail]"<<endl;
	cout<<endl;
	cout<<endl;
	cout<<endl;

	cout<<"   本程序只能计算在节点本身是无环图的情况！"<<endl;
		cout<<"注意：必须确保输入的有向图是简单有向图（没有环，路径权重非负），并且必须有且只有一个开始节点，如果原始图有多个开始节点的话，就需要添加一个虚的开始节点来连接原始多个开始节点。同样，必须添加一个虚的结束节点连接所有原始结束节点。";
	cout<<endl;
	cout<<endl;
	cout<<endl;

	cout<<"提示：输入时请输入图的邻接矩阵"<<endl;
	cout<<endl;
	cout<<endl;
	cout<<"正在初始化............................................................"<<endl;
	cout<<endl;

//!!!!!!!初始化结束
	cout<<"程序计算开始:"<<endl;

	cout<<"请输入节点的个数!";
	cin>>my_vexnum;
	cout<<endl;
	
	cout<<"请输入开始节点!";
	cout<<endl;

	cin>>my_start;
	cout<<endl;
	cout<<"请输入结束节点!";
	cin>>my_end;
	cout<<endl;
int *used = new int [my_vexnum];
for(int i=0;i<my_vexnum;i++)
		used[i] = 0;

	double** array = new double*[my_vexnum];
	for(int i=0;i<my_vexnum;i++)
		array[i] = new double[my_vexnum];
	//cout<<my_vexnum<<endl;
	cout<<"是否使用默认测试矩阵(Y/N)"<<endl;
	cin>>t;
	if(t=='n'||t=='N')
	{
	my_dag = new double *[my_vexnum];
	for(int i=0;i<my_vexnum;i++)
		my_dag[i] = new double [my_vexnum];
for(int i=0;i<my_vexnum;i++)
for(int j=0;j<my_vexnum;j++)
{cout<<"请输入"<<i+1<<"到"<<j+1<<"节点的权值!"<<endl;
cin>>my_dag[i][j];
}
for(int i=0;i<my_vexnum;i++)
for(int j=0;j<my_vexnum;j++)
{
cout<<my_dag[i][j]<<endl;

}
for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			array[i][j] =my_dag[i][j];
	}
	else {

	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			array[i][j] =dag[i][j];
	}
	
	

/*
	// Find the shortest path
	Graph::path_t path;
	unsigned size = 0;
	double min = graph.Dijkstra(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 i=0;i<num;i++)
		cout<<"测试值"<<my_save[i]<<endl;

	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;


	// Find the k shortest paths
Graph::path_list paths;
	int k = graph.MSAforKSP(10,paths);
	cout << "k = " << k << endl;	
my_data = new double *[k];//用来初始话存储K条最短路的节点
	for(int i=0;i<k;i++)
		my_data[i] = new double [k];
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<N;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<N;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;
}

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

*/

Graph graph((double**)array,my_vexnum);

	for(unsigned i=0;i<my_vexnum;i++)//用来计算所有i到j节点的数据
{
for(unsigned j=0;j<my_vexnum;j++)

{double num=0;

	if(i!=j) 
	{//n=graph.zuiduan(i,j,path,my_save,my_vexnum,dag); 
	//返回最短的路的权值
	//cout<<n;
		
double **my_data=NULL;
	
		double num=graph.kkk((double**)array, i,my_vexnum,j,used);//(初始化数组，开始节点，节点个数，结束节点)
delete my_data;
		}
}

	}

/*Graph::path_list paths;
double** subarray = new double*[my_vexnum];
	for(int i=0;i<my_vexnum;i++)
		subarray[i] = new double[my_vexnum];
	for(int i=0;i<my_vexnum;i++)
		for(int j=0;j<my_vexnum;j++)
			subarray[i][j] =dag[i][j];

int k = graph.MSAforKSP(10,paths);
graph.tiaoshu(k,my_vexnum,distroad ,paths,subarray,i);

//k=graph.tiaoshu(dag,my_vexnum,n,k,paths);
//cout<<k;

*/
cout<<"所有节点被最短路径经过的次数!";
for(int i=0;i<my_vexnum;i++)
{
	
cout<<used[i]<<" ";
}
cout<<endl;
delete used;

	for(int i=0;i<N;i++)
		delete[] array[i];
	delete[] array;

	return 0;
	}