最短路径之弗洛伊德算法(Floyd)
#include <string>
#include <iostream>
#include <iterator>
#include <list>
#include <algorithm>
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<int>::iterator begin,list<int>::iterator end,list<int> &l)
{//路径搜索
Rout &r = (*Matrix::MatrixMap)[*begin][*end];
if(r.exitMilestone)
{
list<int>::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<<"输入错误"<<endl;
return ;
}
Rout* r = &(*Matrix::MatrixMap)[i][j];
cout<<start<<"到"<<end<<"最短站点数为:"<<r->power+1<<endl;
list<int> Station;
Station.push_back(i);
Station.push_back(j);
this->SearchMap(Station.begin(),++Station.begin(),Station);
cout<<"途中经过的站为:";
for(list<int>::iterator begin = Station.begin();begin != Station.end();++begin)
{
cout<<RoutingName[*begin]<<" ";
}
cout<<endl;
}
};
Rout(*Matrix::MatrixMap)[Matrix::MAXSIZE][Matrix::MAXSIZE]
= (Rout (*)[Matrix::MAXSIZE][Matrix::MAXSIZE])Matrix::InitMatrixMap();//初始化
int main(int argc, char* argv[])
{
Matrix::Floyd();
string start,end;
cout<<"输入起点和终点"<<endl;
cin>>start>>end;
Matrix(start,end).GetBestRouting();
system("pause");
Matrix::DeleteMatrix();
return 0;
}
补充：软件开发 , C++ ,
