公园导游问题.cpp

公园导游图 给出一张某公园的导游图（景点不少于10个）

//动态规划法之公园导游问题
//程序源代码
#include<iostream.h>
#define MAX 100
int n;                                         //公园景点个数 
template<class T>                              //定义模板 
class Sample                                   //定义Sample为类模板
{
	T park[MAX][MAX],cost[MAX][MAX],path[MAX][MAX]; 
	//park[n][n]是记录公园景点图的成本邻接矩阵；cost[i][j]是记录vi到vj的最小成本路径的长度；
    //path[i][j]是记录最小成本的路径。
	public:
	    Sample(){n=0;}
		void getdata ();                       //数据输入函数
		void shortestpaths();                  //求最短路径函数
		void display();                        //结果输出函数 
};
		template<class T>
		void Sample<T>::getdata ()             //数据输入
		{
			int i,j;
			cout<<"公园景点的个数为：";
			cin>>n;
			cout<<"请输入公园景点的邻接矩阵："<<endl;
			for(i=1;i<=n;i++)
			{	cout<<"请输入公园景点"<<i<<"到其它景点的距离：";
                 for(j=1;j<=n;j++)
				 {
					 cin>>park[i][j];
				 }
				 cout<<endl;
			}
			cout<<"输入的公园景点的邻接矩阵为："<<endl;
            for(i=1;i<=n;i++)
			{
				for(j=1;j<=n;j++)
	                 cout<<park[i][j]<<" ";
                cout<<endl;
			}
			cout<<endl;
		}
		template<class T>
		void Sample<T>::shortestpaths()        //求最短路径
		{
			int i,j,k;
            for (i=1;i<=n; i++) 
                for (j=1;j<=n; j++) 
				{ 
                   if (i==j) cost[i][j]=0;     //顶点本身假设无路径 
				   else 
                        cost[i][j]=park[i][j]; //复制
				   path[i][j]=i;               //初始化路径
				}
            for (k=1; k<=n; k++) 
			{
                for (i=1; i<=n; i++)
				{
                    for (j=1; j<=n; j++) 
					{
                         if (cost[i][k]+cost[k][j]<cost[i][j]) 
						 { 
                             cost[i][j]=cost[i][k]+cost[k][j];  //加入k点
							 if (path[k][j]==k) 
							     path[i][j]=k;
							 else 
								 path[i][j]=path[k][j];         //加入k点后修改路径
						 }
					}
				}
			}
			cout<<"最小成本路径长度的邻接矩阵为："<<endl;;
			for (i=1;i<=n;i++)
			{
				for (j=1;j<=n;j++)
					cout<<cost[i][j]<<" "; 
				cout<<endl;
            }
			cout<<endl;
			cout<<"相应的路径邻接矩阵为："<<endl;
            for (i=1;i<=n;i++)
			{
				for (j=1;j<=n;j++)
					cout<<path[i][j]<<" ";
				cout<<endl;
			}
			cout<<endl;
		}
		template<class T>
		void Sample<T>::display()              //结果输出
		{	
			char time;                         //time控制输入选择景点的次数
			time='Y';
			while (time=='Y')               
			{
			int s,t;
			cout<<"请输入两个景点：";
				cin>>s>>t;                     //任意输入两个景点
            cout<<"两个景点之间的最短路径长度为："<<cost[s][t]<<endl;
            cout<<"相应的走法为：";
			while (s!=t)
			{
				cout<<t<<"<-";                 //采用从后向前标记路径
				t=path[s][t];
			}
		  cout<<s<<endl;
		  cout<<"是否继续？（如果继续，请输入Y，否则请输入NO）：";
		     cin>>time;                        //键入Y，可以多次选择景点 
			}
		}
        void main()                            //主函数
		{
			Sample<int> a;                     //声明一个模板类的对象a
			a.getdata();                       //通过访问对象的公有成员函数，实现数据输入
	        a.shortestpaths();                 //求解最短路径
	        a.display();                       //输出结果，即最短路径值和相应的走法
		
		}