pathhead.h

算法作业,迪杰斯特拉算法模拟公车选路,任选图上两点算出经过的最少站点数和最短路径及最短路径长度

#include "stdafx.h"
#define N 7
#define INI 10000
class CPath
{
public:
	void lesstime(float (*g)[N],int m,int n,int sp)//时间最少路径
	{
		path(g,m,n,(float)(0.1*sp));     //每站停0.1h相当于每过一站多行0.1*sp千米
//		mm=m;nn=n;
	//	output();
	}
	void lesspoint(float (*g)[N],int m,int n)//站点最少路径
	{
		int i,j;
		float p[N][N];                        //新图使各站点间距离相等
		for(i=0;i<N;i++)
			for(j=0;j<N;j++)
				if(*(*(g+i)+j)>0&&*(*(g+i)+j)<INI)
					p[i][j]=1;
				else
					p[i][j]=*(*(g+i)+j);
		path(p,m,n,0);                //站点最少即无向图不带权的情况
//		mm=m;
//		nn=n;
//		output();
	}

	void path(float (*g)[N],int m,int n,float k)  //计算最优路径的函数
	{
		int i,j,a[N];               
		float t[N];                          //记录最优距离
		//初始化
		for(i=0;i<N;i++)
		{
			t[i]=*(*(g+m)+i);                 //初始化最优距离
			a[i]=m;                 //a未初始化    //记录i站点的前驱(初始化为起始点)
		}
		//计算最优路径和距离
		for(i=1;i<N+n;i++)
			if((i+m)%N!=n)                    //终止点不用计算
				for(j=0;j<N;j++)
					if((j!=(i+m)%N)&&(j!=m))    //跳过自己到自己最优路径的计算
						if(t[(i+m)%N]+*(*(g+(i+m)%N)+j)+k<t[j])//若站点i到站点j距离较优则更新
						{
							t[j]=t[(i+m)%N]+*(*(g+(i+m)%N)+j)+k;//更新最优距离
							a[j]=(i+m)%N;                       //更新j站点前驱为i
						}

	
		distance=t[n];		                                 //到终点最优距离			
		i=n;                     //误写为m
		j=0;
		//保存最优路径
		while(a[i]!=m)                                        //保存最优路径到b[]
		{
			b[j]=a[i];                                        //a[i]点前驱保存到b[j]
			j++;
			i=a[i];                                           //i改记为a[i]的前驱站点 
		}
		len=j-1;                                              //最优路径经过站点数
		mm=m;nn=n;
//		cout<<m<<"->";
//		for(i=j-1;i>=0;i--)      //误将i从小到大输出（出来是反的）
//			cout<<b[i]<<"->";
//		cout<<n<<endl;
	}
/*	void output()
	{
		cout<<mm<<"->";
		for(int i=len;i>=0;i--)      //误将i从小到大输出（出来是反的）
			cout<<b[i]<<"->";
		cout<<nn<<endl;
		cout<<distance<<endl;
	}*/
	int* getpath()                           //返回最优路径站点经过记录数组
	{
		return b;
	}
	int getlen()                             //返回经过站点数
	{
		return len;
	}
	float getdistance()                       //返回最优距离
	{
		return distance;
	}
	CString outputpath()                     //路径输出
	{
		CString p,s;
		char k;
		s="->";
		p.Format("%d",mm);
		p=p+s;
		for(int i=len;i>=0;i--){           //输出经过站点顺序
			k=(char)b[i]+48;
			p=p+k;
			p=p+s;
		}
		k=(char)nn+48;
		p=p+k;
		return p;
	}
private:
	float distance;
	int len,b[N];
	int mm,nn;
};