公交线路提示(课设)-创新互联

[问题描述]

创新互联公司是一家专业从事网站建设、网络营销、小程序设计、网站运营为一体的建站企业;在网站建设告别千篇一律,告别似曾相识,这一次我们重新定义网站建设,让您的网站别具一格。成都响应式网站建设公司,实现全网营销!一站适应多终端,一样的建站,不一样的体验!

根据真实南京公交线路图,建立南京主要公交线路图的存储结构。

[基本要求]

(1)输入任意两站点,给出转车次数最少的乘车路线。

(2)输入任意两站点,给出经过站点最少的乘车路线。

这道题的实际应性比较强,要从文件里读取大量数据来实现,文件内容(部分)如下图所示:

即使从大量的数据中我们也可以看出,这道题还是比较有难度的。 我的解题思路如下:

既然要用图,首先就应该考虑把什么数据作为图上的结点。既然是对任意两个站点进行操作,所以这里的结点应该是各站点。这里我们采用邻接表的数据结构来构建图,对每个站点我们要保存其名称以及站点编号(按创建时候的顺序来编)。第一步当然是打开文件,打开文本文件后,依次读取每一行数据,然后处理数据(这一步并不难,但比较繁琐,需要细心和耐心)。

以上都是基本操作,接下来才是需要思考的地方。首先这道题有两问,这两问本质上都和求最短路径有关,只是“最短路径”的含义不一样。第一问是指转车次数最少的距离,而第二问是指经过站点最少的距离。所以,我们要创建两张邻接表。第一张邻接表G1,我们把边定义为:同一条公交线路上的两点之间存在边(这里边的权值均为1);第二张邻接表G2,我们把边定义为:相邻两站之间存在边。这就是两个图主要的区别,使用的结构体是一致的,只是在建立邻接表时对边的处理方式不同。

下面,如何来求最短路径?相信大家都会想到迪杰斯特拉算法,这是求单源最短路径的一个很经典、应用很广泛的算法(不知道的小伙伴可以去看去我之前的文章,有详细解说)。这里我们把相邻点的权值都视为1,然后用迪杰斯特拉算法就可以求出以任意站点为起始点,到其它站点的最短距离。这个”最短距离“在第一问就是指转车次数最少的距离,在第二问是指经过站点最少的距离。

另外需要注意的一点是:一般的迪杰斯特拉算法只用到三个辅助数组,Adjvex 保存从起始站点到达某站点会经过的站点编号;Lowcost 保存从起始站点到某站点的最短距离;Flag 则用来标注某站点是否已被选中(初始化为0)。在这一题中为了求出换乘线路,我又增加了一个 Route 来保存从起始站点到达某站点会经过的路线。

我的代码如下:

1、创建两张邻接表

# include# include# include# include# include# define SIZE 1024
# define NEWSIZE 1024
# define Infinity 100000000   //表示无限大
using namespace std;
typedef struct SiteArcNode {        //边的结点(站点)结构类型
	int adjvex;						//该边的站点编号
	int path;						//站点所在的路线
	struct SiteArcNode* nextarc;	//指向下一条边的指针
}SiteArcNode;
typedef struct SiteVexNode {  //站点结构
	int num;				  //站点编号(从0开始)
	char name[50];            //站点名称
	SiteArcNode* firstarc;    //指向第一条与该站点有关的边的指针
}SiteVexNode;
typedef struct SiteGraph {    //站点的邻接表结构类型
	SiteVexNode* SVNode;      //定义邻接表
	int vexnum;			      //站点数
	int size;                 //邻接表的大小
}SiteGraph;

//这里的最短距离可以指经过站点最少的距离,也可以指转车次数最少的距离
int* Route;     //从起始站点到达某站点会经过的路线
int* Adjvex;    //从起始站点到达某站点会经过的站点编号
int* Lowcost;   //从起始站点到某站点的最短距离
int* Flag;      //标注站点是否已被选中(初始化为0)
void Create(SiteGraph& G1, SiteGraph& G2); //创建两张图(G1:连接同一路线上的站点;G2:连接相邻站点)
void Dijkstra(SiteGraph G1, int v);        //迪杰斯特拉算法求单源最短路线
void Find_Route(SiteGraph G1);             //对任意两站点,给出转车次数最少的乘车路线
void Find_Site(SiteGraph G2);              //对任意两站点,给出经过站点最少的乘车路线
void Print_Path(SiteGraph G, int v1, int v2, string s1);  //打印路线

void Create(SiteGraph& G1, SiteGraph& G2)    //创建图
{
	fstream file;
	char s[1000];
	G1.SVNode = (SiteVexNode*)malloc(SIZE * sizeof(SiteVexNode));
	G2.SVNode = (SiteVexNode*)malloc(SIZE * sizeof(SiteVexNode));
	G1.size = SIZE;
	G2.size = SIZE;
	G1.vexnum = 0;
	G2.vexnum = 0;
	file.open("南京公交线路.txt", ios::in);
	if (file.fail()) {
		cout<< "文件打开失败"<< endl;
		exit(0);
	}
	file.getline(s, 1000);
	while (!file.eof()) {
		int t = 1, a = 0, k = 0;
		vectorM; //保存这条线路上的所有站点编号
		char site[50];
		for (int i = 0; i< strlen(s); i++) {
			if (s[i] == ' ') {
				t = 0;
			}
			else if (t && (s[i] >= 48 && s[i]<= 57)) {
				a = a * 10 + s[i] - 48;
			}
			else if (!t) {
				//开始处理站点数据
				if (s[i] == ',') {
					//遇到“,”说明一个站点已输入完毕,建立该站点的结点
					site[k] = '\0';
					k = 0;
					int t1 = 1;
					int n;   //当前站点的编号
					for (int j = 0; j< G2.vexnum; j++) {
						//先查看该站点是否已建立头结点
						if (strcmp(G2.SVNode[j].name, site) == 0) {
							t1 = 0;  //该站点已建立头结点,t1标注为0
							n = j;   //n=当前站点的编号
							break;
						}
					}
					if (t1) {
						//该站点未建立头结点
						if (G1.size<= G1.vexnum) {
							//根据点的个数动态分配空间
							G1.SVNode = (SiteVexNode*)realloc(G1.SVNode, (G1.size + NEWSIZE) * sizeof(SiteVexNode));
							G1.size += NEWSIZE;
						}
						if (G2.size<= G2.vexnum) {
							//根据点的个数动态分配空间
							G2.SVNode = (SiteVexNode*)realloc(G2.SVNode, (G2.size + NEWSIZE) * sizeof(SiteVexNode));
							G2.size += NEWSIZE;
						}
						strcpy(G1.SVNode[G1.vexnum].name, site); //头结点名称
						strcpy(G2.SVNode[G2.vexnum].name, site); //头结点名称
						G1.SVNode[G1.vexnum].num = G1.vexnum;    //头结点编号
						G2.SVNode[G2.vexnum].num = G2.vexnum;    //头结点编号
						G1.SVNode[G1.vexnum].firstarc = NULL;
						G2.SVNode[G2.vexnum].firstarc = NULL;
						n = G2.vexnum;  //n=当前站点的编号
						G1.vexnum++;
						G2.vexnum++;
					}
					if (!M.empty()) {
						//如果不是这条线路上的第一个站点
						SiteArcNode* p, * q;
						//不是第一个站点,G1表要与这条线路上的所有站点建立连接
						for (int j = 0; j< M.size(); j++) {
							//当前站点加入到前面所有站点的链表中
							p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //创建一个用于存放当前边的结点p
							p->nextarc = NULL;
							p->adjvex = n;
							p->path = a;  //保存这条边所在的线路
							q = G1.SVNode[M[j]].firstarc;
							//将边按顺序插入到链表末尾
							if (q == NULL) {
								G1.SVNode[M[j]].firstarc = p;
							}
							else {
								while (q->nextarc != NULL) {
									q = q->nextarc;
								}
								q->nextarc = p;
							}
							//前面所有站点加入到当前站点的链表中
							p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //创建一个用于存放当前边的结点p
							p->nextarc = NULL;
							p->adjvex = M[j];
							p->path = a;   //保存这条边所在的线路
							q = G1.SVNode[n].firstarc;  //前一个站点加入到当前站点的链表中
							//将边按顺序插入到链表末尾
							if (q == NULL) {
								G1.SVNode[n].firstarc = p;
							}
							else {
								while (q->nextarc != NULL) {
									q = q->nextarc;
								}
								q->nextarc = p;
							}
						}
						//不是第一个站点,G2表要与前一个站点建立连接
						int m = M[M.size() - 1];
						p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //创建一个用于存放当前边的结点p
						p->nextarc = NULL;
						p->adjvex = n;
						p->path = a;
						q = G2.SVNode[m].firstarc;  //当前站点加入到前一个站点的链表中
						//将边按顺序插入到链表末尾
						if (q == NULL) {
							G2.SVNode[m].firstarc = p;
						}
						else {
							while (q->nextarc != NULL) {
								q = q->nextarc;
							}
							q->nextarc = p;
						}
						p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //创建一个用于存放当前边的结点p
						p->nextarc = NULL;
						p->adjvex = m;
						p->path = a;
						q = G2.SVNode[n].firstarc;  //前一个站点加入到当前站点的链表中
						//将边按顺序插入到链表末尾
						if (q == NULL) {
							G2.SVNode[n].firstarc = p;
						}
						else {
							while (q->nextarc != NULL) {
								q = q->nextarc;
							}
							q->nextarc = p;
						}
					}
					M.push_back(n);
				}
				else {
					site[k] = s[i];
					k++;
				}
			}
		}
		file.getline(s, 1000);
	}
	file.close();
}

2、求解问题1和问题2

void Dijkstra(SiteGraph G, int v)  //迪杰斯特拉算法求单源最短路线
{
	Lowcost[v] = 0;          //初始站点到初始站点的距离为0
	Flag[v] = 1;             //标注初始点
	int num = 1;             //记录目前被选中的站点数目
	SiteArcNode* p;
	while (num< G.vexnum) {
		p = G.SVNode[v].firstarc;  //p为新选中的点的第一个邻接点
		while (p != NULL) {
			//由于新点加入,更新起始点与其余未被选中的顶点之间的距离
			if (!Flag[p->adjvex] && Lowcost[p->adjvex] >Lowcost[v] + 1) {
				Lowcost[p->adjvex] = Lowcost[v] + 1;
				Adjvex[p->adjvex] = v;
				Route[p->adjvex] = p->path;  //保存该站点所在的路线
			}
			p = p->nextarc;
		}
		int min = Infinity;
		for (int i = 1; i<= G.vexnum; i++) {
			//从未选择的站点中找下一个与起始站点距离最近的站点
			if (!Flag[i] && Lowcost[i]< min) {
				min = Lowcost[i];
				v = i;               //更新v为目前与起始站点距离最近的站点
			}
		}
		Flag[v] = 1;             //标记新选中的站点
		num++;                   //目前被选中的站点数目+1
	}
}

void Print_Path(SiteGraph G, int v1, int v2, string s1)   //打印路线
{
	cout<< "路径为:"<< endl;
	int j = v2;
	vectorPath;
	while (j != v1) {
		Path.push_back(j);
		j = Adjvex[j];
	}
	int k = Route[Path[Path.size() - 1]];
	cout<< k<< "路:"<< s1;
	for (int i = Path.size() - 1; i >= 0; i--) {
		if (Route[Path[i]] != k) {
			k = Route[Path[i]];
			cout<< "\n换乘到"<< k<< "路:"<< G.SVNode[Path[i + 1]].name;
		}
		cout<< "->"<< G.SVNode[Path[i]].name;
	}
	cout<< endl;
}

void Find_Route(SiteGraph G)     //对任意两站点,给出转车次数最少的乘车路线
{
	string s1, s2;
	int v1, v2;
	cout<< "请输入第一个站点:";
	cin >>s1;
	cout<< "请输入第二个站点:";
	cin >>s2;
	for (int i = 0; i< G.vexnum; i++) {
		if (G.SVNode[i].name == s1) {
			v1 = i;
		}
		if (G.SVNode[i].name == s2) {
			v2 = i;
		}
	}
	for (int i = 1; i<= G.vexnum; i++) {
		//初始化
		Adjvex[i] = v1;
		Route[i] = 0;
		Lowcost[i] = Infinity;
		Flag[i] = 0;
	}
	Dijkstra(G, v1);   //求从站点v1出发到站点v2的换乘次数最少的乘车路线
	cout<< endl;
	cout<< s1<< " 到 "<< s2<< " 的换乘次数最少为"<< Lowcost[v2] - 1<< "  ";  //换乘次数要减1
	//输出起始点到站点v2的最少转车路径
	Print_Path(G, v1, v2, s1);
}

void Find_Site(SiteGraph G)      //对任意两站点,给出经过站点最少的乘车路线
{
	string s1, s2;
	int v1, v2;
	cout<< "请输入第一个站点:";
	cin >>s1;
	cout<< "请输入第二个站点:";
	cin >>s2;
	for (int i = 0; i< G.vexnum; i++) {
		if (G.SVNode[i].name == s1) {
			v1 = i;
		}
		if (G.SVNode[i].name == s2) {
			v2 = i;
		}
	}
	for (int i = 1; i<= G.vexnum; i++) {
		//初始化
		Adjvex[i] = v1;
		Route[i] = 0;
		Lowcost[i] = Infinity;
		Flag[i] = 0;
	}
	Dijkstra(G, v1);   //求从站点v1出发到站点v2的经过站点最少的乘车路线
	//输出起始站点到站点v2的最短距离
	cout<< endl;
	cout<< s1<< " 到 "<< s2<< " 的经过站点次数最少为"<< Lowcost[v2] + 1<< "  ";
	//输出起始点到站点v2的最少转车路径
	Print_Path(G, v1, v2, s1);
}

全部代码:

# include# include# include# include# include# define SIZE 1024
# define NEWSIZE 1024
# define Infinity 100000000   //表示无限大
using namespace std;
typedef struct SiteArcNode {        //边的结点(站点)结构类型
	int adjvex;						//该边的站点编号
	int path;						//站点所在的路线
	struct SiteArcNode* nextarc;	//指向下一条边的指针
}SiteArcNode;
typedef struct SiteVexNode {  //站点结构
	int num;				  //站点编号(从0开始)
	char name[50];            //站点名称
	SiteArcNode* firstarc;    //指向第一条与该站点有关的边的指针
}SiteVexNode;
typedef struct SiteGraph {    //站点的邻接表结构类型
	SiteVexNode* SVNode;      //定义邻接表
	int vexnum;			      //站点数
	int size;                 //邻接表的大小
}SiteGraph;

//这里的最短距离可以指经过站点最少的距离,也可以指转车次数最少的距离
int* Route;     //从起始站点到达某站点会经过的路线
int* Adjvex;    //从起始站点到达某站点会经过的站点编号
int* Lowcost;   //从起始站点到某站点的最短距离
int* Flag;      //标注站点是否已被选中(初始化为0)
void Create(SiteGraph& G1, SiteGraph& G2); //创建两张图(G1:连接同一路线上的站点;G2:连接相邻站点)
void Dijkstra(SiteGraph G1, int v);        //迪杰斯特拉算法求单源最短路线
void Find_Route(SiteGraph G1);             //对任意两站点,给出转车次数最少的乘车路线
void Find_Site(SiteGraph G2);              //对任意两站点,给出经过站点最少的乘车路线
void Print_Path(SiteGraph G, int v1, int v2, string s1);  //打印路线

int main()
{
	SiteGraph G1, G2;
	Create(G1, G2);
	//动态创建辅助数组
	Adjvex = (int*)malloc((G1.vexnum + 10) * sizeof(int));
	Route = (int*)malloc((G1.vexnum + 10) * sizeof(int));
	Lowcost = (int*)malloc((G1.vexnum + 10) * sizeof(int));
	Flag = (int*)malloc((G1.vexnum + 10) * sizeof(int));
	cout<< "(1)输入任意两站点,给出转车次数最少的乘车路线"<< endl;
	Find_Route(G1);
	cout<< endl;
	cout<< "*********************************************************************************\n";
	cout<< endl;
	cout<< "(2)输入任意两站点,给出经过站点最少的乘车路线"<< endl;
	Find_Site(G2);
	return 0;
}

void Create(SiteGraph& G1, SiteGraph& G2)    //创建图
{
	fstream file;
	char s[1000];
	G1.SVNode = (SiteVexNode*)malloc(SIZE * sizeof(SiteVexNode));
	G2.SVNode = (SiteVexNode*)malloc(SIZE * sizeof(SiteVexNode));
	G1.size = SIZE;
	G2.size = SIZE;
	G1.vexnum = 0;
	G2.vexnum = 0;
	file.open("南京公交线路.txt", ios::in);
	if (file.fail()) {
		cout<< "文件打开失败"<< endl;
		exit(0);
	}
	file.getline(s, 1000);
	while (!file.eof()) {
		int t = 1, a = 0, k = 0;
		vectorM; //保存这条线路上的所有站点编号
		char site[50];
		for (int i = 0; i< strlen(s); i++) {
			if (s[i] == ' ') {
				t = 0;
			}
			else if (t && (s[i] >= 48 && s[i]<= 57)) {
				a = a * 10 + s[i] - 48;
			}
			else if (!t) {
				//开始处理站点数据
				if (s[i] == ',') {
					//遇到“,”说明一个站点已输入完毕,建立该站点的结点
					site[k] = '\0';
					k = 0;
					int t1 = 1;
					int n;   //当前站点的编号
					for (int j = 0; j< G2.vexnum; j++) {
						//先查看该站点是否已建立头结点
						if (strcmp(G2.SVNode[j].name, site) == 0) {
							t1 = 0;  //该站点已建立头结点,t1标注为0
							n = j;   //n=当前站点的编号
							break;
						}
					}
					if (t1) {
						//该站点未建立头结点
						if (G1.size<= G1.vexnum) {
							//根据点的个数动态分配空间
							G1.SVNode = (SiteVexNode*)realloc(G1.SVNode, (G1.size + NEWSIZE) * sizeof(SiteVexNode));
							G1.size += NEWSIZE;
						}
						if (G2.size<= G2.vexnum) {
							//根据点的个数动态分配空间
							G2.SVNode = (SiteVexNode*)realloc(G2.SVNode, (G2.size + NEWSIZE) * sizeof(SiteVexNode));
							G2.size += NEWSIZE;
						}
						strcpy(G1.SVNode[G1.vexnum].name, site); //头结点名称
						strcpy(G2.SVNode[G2.vexnum].name, site); //头结点名称
						G1.SVNode[G1.vexnum].num = G1.vexnum;    //头结点编号
						G2.SVNode[G2.vexnum].num = G2.vexnum;    //头结点编号
						G1.SVNode[G1.vexnum].firstarc = NULL;
						G2.SVNode[G2.vexnum].firstarc = NULL;
						n = G2.vexnum;  //n=当前站点的编号
						G1.vexnum++;
						G2.vexnum++;
					}
					if (!M.empty()) {
						//如果不是这条线路上的第一个站点
						SiteArcNode* p, * q;
						//不是第一个站点,G1表要与这条线路上的所有站点建立连接
						for (int j = 0; j< M.size(); j++) {
							//当前站点加入到前面所有站点的链表中
							p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //创建一个用于存放当前边的结点p
							p->nextarc = NULL;
							p->adjvex = n;
							p->path = a;  //保存这条边所在的线路
							q = G1.SVNode[M[j]].firstarc;
							//将边按顺序插入到链表末尾
							if (q == NULL) {
								G1.SVNode[M[j]].firstarc = p;
							}
							else {
								while (q->nextarc != NULL) {
									q = q->nextarc;
								}
								q->nextarc = p;
							}
							//前面所有站点加入到当前站点的链表中
							p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //创建一个用于存放当前边的结点p
							p->nextarc = NULL;
							p->adjvex = M[j];
							p->path = a;   //保存这条边所在的线路
							q = G1.SVNode[n].firstarc;  //前一个站点加入到当前站点的链表中
							//将边按顺序插入到链表末尾
							if (q == NULL) {
								G1.SVNode[n].firstarc = p;
							}
							else {
								while (q->nextarc != NULL) {
									q = q->nextarc;
								}
								q->nextarc = p;
							}
						}
						//不是第一个站点,G2表要与前一个站点建立连接
						int m = M[M.size() - 1];
						p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //创建一个用于存放当前边的结点p
						p->nextarc = NULL;
						p->adjvex = n;
						p->path = a;
						q = G2.SVNode[m].firstarc;  //当前站点加入到前一个站点的链表中
						//将边按顺序插入到链表末尾
						if (q == NULL) {
							G2.SVNode[m].firstarc = p;
						}
						else {
							while (q->nextarc != NULL) {
								q = q->nextarc;
							}
							q->nextarc = p;
						}
						p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //创建一个用于存放当前边的结点p
						p->nextarc = NULL;
						p->adjvex = m;
						p->path = a;
						q = G2.SVNode[n].firstarc;  //前一个站点加入到当前站点的链表中
						//将边按顺序插入到链表末尾
						if (q == NULL) {
							G2.SVNode[n].firstarc = p;
						}
						else {
							while (q->nextarc != NULL) {
								q = q->nextarc;
							}
							q->nextarc = p;
						}
					}
					M.push_back(n);
				}
				else {
					site[k] = s[i];
					k++;
				}
			}
		}
		file.getline(s, 1000);
	}
	file.close();
}

void Dijkstra(SiteGraph G, int v)  //迪杰斯特拉算法求单源最短路线
{
	Lowcost[v] = 0;          //初始站点到初始站点的距离为0
	Flag[v] = 1;             //标注初始点
	int num = 1;             //记录目前被选中的站点数目
	SiteArcNode* p;
	while (num< G.vexnum) {
		p = G.SVNode[v].firstarc;  //p为新选中的点的第一个邻接点
		while (p != NULL) {
			//由于新点加入,更新起始点与其余未被选中的顶点之间的距离
			if (!Flag[p->adjvex] && Lowcost[p->adjvex] >Lowcost[v] + 1) {
				Lowcost[p->adjvex] = Lowcost[v] + 1;
				Adjvex[p->adjvex] = v;
				Route[p->adjvex] = p->path;  //保存该站点所在的路线
			}
			p = p->nextarc;
		}
		int min = Infinity;
		for (int i = 1; i<= G.vexnum; i++) {
			//从未选择的站点中找下一个与起始站点距离最近的站点
			if (!Flag[i] && Lowcost[i]< min) {
				min = Lowcost[i];
				v = i;               //更新v为目前与起始站点距离最近的站点
			}
		}
		Flag[v] = 1;             //标记新选中的站点
		num++;                   //目前被选中的站点数目+1
	}
}

void Print_Path(SiteGraph G, int v1, int v2, string s1)   //打印路线
{
	cout<< "路径为:"<< endl;
	int j = v2;
	vectorPath;
	while (j != v1) {
		Path.push_back(j);
		j = Adjvex[j];
	}
	int k = Route[Path[Path.size() - 1]];
	cout<< k<< "路:"<< s1;
	for (int i = Path.size() - 1; i >= 0; i--) {
		if (Route[Path[i]] != k) {
			k = Route[Path[i]];
			cout<< "\n换乘到"<< k<< "路:"<< G.SVNode[Path[i + 1]].name;
		}
		cout<< "->"<< G.SVNode[Path[i]].name;
	}
	cout<< endl;
}

void Find_Route(SiteGraph G)     //对任意两站点,给出转车次数最少的乘车路线
{
	string s1, s2;
	int v1, v2;
	cout<< "请输入第一个站点:";
	cin >>s1;
	cout<< "请输入第二个站点:";
	cin >>s2;
	for (int i = 0; i< G.vexnum; i++) {
		if (G.SVNode[i].name == s1) {
			v1 = i;
		}
		if (G.SVNode[i].name == s2) {
			v2 = i;
		}
	}
	for (int i = 1; i<= G.vexnum; i++) {
		//初始化
		Adjvex[i] = v1;
		Route[i] = 0;
		Lowcost[i] = Infinity;
		Flag[i] = 0;
	}
	Dijkstra(G, v1);   //求从站点v1出发到站点v2的换乘次数最少的乘车路线
	cout<< endl;
	cout<< s1<< " 到 "<< s2<< " 的换乘次数最少为"<< Lowcost[v2] - 1<< "  ";  //换乘次数要减1
	//输出起始点到站点v2的最少转车路径
	Print_Path(G, v1, v2, s1);
}

void Find_Site(SiteGraph G)      //对任意两站点,给出经过站点最少的乘车路线
{
	string s1, s2;
	int v1, v2;
	cout<< "请输入第一个站点:";
	cin >>s1;
	cout<< "请输入第二个站点:";
	cin >>s2;
	for (int i = 0; i< G.vexnum; i++) {
		if (G.SVNode[i].name == s1) {
			v1 = i;
		}
		if (G.SVNode[i].name == s2) {
			v2 = i;
		}
	}
	for (int i = 1; i<= G.vexnum; i++) {
		//初始化
		Adjvex[i] = v1;
		Route[i] = 0;
		Lowcost[i] = Infinity;
		Flag[i] = 0;
	}
	Dijkstra(G, v1);   //求从站点v1出发到站点v2的经过站点最少的乘车路线
	//输出起始站点到站点v2的最短距离
	cout<< endl;
	cout<< s1<< " 到 "<< s2<< " 的经过站点次数最少为"<< Lowcost[v2] + 1<< "  ";
	//输出起始点到站点v2的最少转车路径
	Print_Path(G, v1, v2, s1);
}

运行结果:

(1)输入任意两站点,给出转车次数最少的乘车路线
请输入第一个站点:白马公园站
请输入第二个站点:樱花路站

白马公园站 到 樱花路站 的换乘次数最少为1  路径为:
20路:白马公园站->北京东路九华山站
换乘到11路:北京东路九华山站->樱花路站

*********************************************************************************

(2)输入任意两站点,给出经过站点最少的乘车路线
请输入第一个站点:白马公园站
请输入第二个站点:樱花路站

白马公园站 到 樱花路站 的经过站点次数最少为8  路径为:
20路:白马公园站->太平门站
换乘到11路:太平门站->板仓街岗子村站
换乘到6路:板仓街岗子村站->板仓村站->板仓街花园路站->樱驼村站->蒋王庙站->樱花路站

这里我采用的数据结构是邻接表,当然也可以使用邻接矩阵,基本方法是不变的。不过使用邻接矩阵会浪费大量的空间,运行时也会比邻接表慢,所以建议使用邻接表。这道题虽然相对复杂,但贴近生活实际,对于大家熟悉和应用迪杰斯特拉算法有很大的帮助。

以上便是我对这道题的思考,很高兴能与大家分享。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前名称:公交线路提示(课设)-创新互联
分享路径:http://scyanting.com/article/ephee.html