最短路径之弗洛伊德算法(Floyd)

#include 
#include 
#include 
#include 
#include 
using namespace std;
//问题描述
//
//高级题：地铁换乘
//已知2条地铁线路，其中A为环线，B为东西向线路，线路都是双向的。经过的站点名分别如下，两条线交叉的换乘点用T1、T2表示。编写程序，任意输入两个站点名称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。
//地铁线A（环线）经过车站：A1  A2  A3  A4  A5  A6  A7  A8  A9  T1  A10  A11  A12  A13  T2  A14  A15  A16  A17  A18
//地铁线A（直线）经过车站：B1  B2  B3  B4  B5  T1  B6  B7  B8  B9  B10  T2  B11  B12  B13  B14  B15
//
//输入：输入两个不同的站名
//输出：输出最少经过的站数,含输入的起点和终点，换乘站点只计算一次

const static string RoutingName[] = {"A1","A2","A3","A4","A5","A6","A7","A8","A9","A10",  
										"A11","A12","A13","A14","A15","A16","A17","A18",  
									 "B1","B2","B3","B4","B5","B6","B7","B8","B9","B10",  
									 "B11","B12","B13","B14","B15","T1","T2"};
const static unsigned int DotNumber = sizeof(RoutingName)/sizeof(string);
//路
class Rout
{
public:
	int power;//权值
	bool exitMilestone;//是否存在拐点
	int milestone;//拐点
	Rout():exitMilestone(false){};
};
//邻接矩阵
class Matrix
{
private:
	string start;//起点
	string end;//终点
	enum
	{
		MAXSIZE=DotNumber//邻接矩阵大小
	};
	void SearchMap(list::iterator begin,list::iterator end,list &l)
	{//路径搜索
		Rout &r = (*Matrix::MatrixMap)[*begin][*end];
		if(r.exitMilestone)
		{
			list::iterator temp = begin;
			l.insert(end,r.milestone);
			SearchMap(temp,++begin,l);
			SearchMap(begin,end,l);
		}
	}
public:
	Matrix(string start,string end):start(start),end(end){};
	static Rout (*MatrixMap)[Matrix::MAXSIZE][Matrix::MAXSIZE];//邻接矩阵指针
	static void* InitMatrixMap()
	{//初始化邻接矩阵
		Rout **p = new Rout*[Matrix::MAXSIZE];
		Rout *temp = new Rout[Matrix::MAXSIZE*Matrix::MAXSIZE];
		//构建连续空间
		for(unsigned int i = 0;i < Matrix::MAXSIZE;++i)
			p[i] = &temp[i*Matrix::MAXSIZE];
		//权值赋值
		for(unsigned int i = 0;i < Matrix::MAXSIZE;++i)
			for(unsigned int j = 0;j < Matrix::MAXSIZE;++j)
			{
				if(i == j)
					p[i][j].power = 0;
				else
					p[i][j].power = 65535;
			}
		const int AR[] = {1,2,3,4,5,6,7,8,9,34,10,11,12,13,35,14,15,16,17,18,1};//A路
		const int BR[] = {19,20,21,22,23,34,24,25,26,27,28,35,29,30,31,32,33};//B路
		for(unsigned int i = 0;i < sizeof(AR)/sizeof(int)-1;++i)
		{
			p[AR[i]-1][AR[i+1]-1].power = 1;
			p[AR[i+1]-1][AR[i]-1].power = 1;
		}
		for(unsigned int i = 0;i < sizeof(BR)/sizeof(int)-1;++i)
		{
			p[BR[i]-1][BR[i+1]-1].power = 1;
			p[BR[i+1]-1][BR[i]-1].power = 1;
		}
		delete[] p;
		return temp;
	}; 
	static void Floyd()
	{//FLOYD算法
		for(int i = 0;i < DotNumber;++i)
			for(int j = 0;j < DotNumber;++j)
				for(int k = 0;k < DotNumber;++k)
				{
					if((*Matrix::MatrixMap)[j][k].power >





 ((*Matrix::MatrixMap)[j][i].power + (*Matrix::MatrixMap)[i][k].power))
					{
						(*Matrix::MatrixMap)[j][k].power = ((*Matrix::MatrixMap)[j][i].power + (*Matrix::MatrixMap)[i][k].power);
						(*Matrix::MatrixMap)[j][k].exitMilestone = true;
						(*Matrix::MatrixMap)[j][k].milestone = i;//记录下拐点
					}
				}
	}
	static void DeleteMatrix()
	{//删除初始数组
		delete [] (Matrix::MatrixMap);
		Matrix::MatrixMap = NULL;
	}
	void GetBestRouting()
	{//得出最短路径
		int i = find(RoutingName,RoutingName+DotNumber,start)-RoutingName,j = find(RoutingName,RoutingName+DotNumber,end)-RoutingName;
		if(i == DotNumber || j == DotNumber)
		{
			cout<<"输入错误"<power+1< Station;
		Station.push_back(i);
		Station.push_back(j);
		this->SearchMap(Station.begin(),++Station.begin(),Station);
		cout<<"途中经过的站为:";
		for(list::iterator begin = Station.begin();begin != Station.end();++begin)
		{
			cout<>start>>end;
	Matrix(start,end).GetBestRouting();
	system("pause");
	Matrix::DeleteMatrix();
	return 0;
}