park.cpp

数据结构第十二次实验 经典的公园最短路径问题 采用从文件中读取邻接表进行构图 具体算法见程序

#include<iostream.h>
#include<fstream.h> 
#include "park.h"

template<class T>
void Sample<T>::getdata ()             
	{
	ifstream infile ("park.dat");
	if(!infile)
	{
		cerr<< "error open"<< endl;
	}
		int i,j;

		cout<<"已从文件输入公园景点的邻接矩阵："<<endl;
		for(i=1;i<=6;i++)
		{	
			for(j=1;j<=6;j++)
			 {
				 infile>>park[i][j];
			 }
		}
		cout<<"输入的公园景点的邻接矩阵为："<<endl;
           for(i=1;i<=6;i++)
		{
			for(j=1;j<=6;j++) 
                cout<<park[i][j]<<"  ";
			cout<<endl;
	}

	cout<<endl;
}


template<class T>
void Sample<T>::ShortPath()      
		{
			int i,j,k;
            for (i=1;i<=6; i++) 
                for (j=1;j<=6; j++) 
				{ 
                   if (i==j) cost[i][j]=0;     //顶点本身假设无路径 
				   else 
                        cost[i][j]=park[i][j]; 
				   path[i][j]=i;               
				}
            for (k=1; k<=6; k++) 
			{
                for (i=1; i<=6; i++)
				{
                    for (j=1; j<=6; 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];         
						 }
		
					}
				}
			}

		cout<<"最小成本路径长度 邻接矩阵："<<endl;;
		for (i=1;i<=6;i++)
		{
			for (j=1;j<=6;j++)
			cout<<cost[i][j]<<" "; 
			cout<<endl;
        }
		cout<<endl;
		cout<<"相应路径 邻接矩阵："<<endl;
        for (i=1;i<=6;i++)
		{
			for (j=1;j<=6;j++)
			cout<<path[i][j]<<" ";
			cout<<endl;
		}
	cout<<endl;
}
template<class T>
void Sample<T>::display()              
{	
		int s,t;
		cout<<"请输入两个景点（1-A,2-B,3-C,4-D,5-E,6-F）：";
		cin>>s>>t;                    
          cout<<"景点间最短路径长度："<<cost[s][t]<<endl;
          cout<<"走法为：";
	while (s!=t)
	{
		cout<<t<<" <-- ";                
		t=path[s][t];
	}
    cout<<s<<endl;
}



void main()                            
{	
	cout << "------------------------------最短路径问题--------------------------------"<<endl;
	Sample<int> a;                     
	a.getdata();                       
    a.ShortPath();                  
    a.display();                       
}